编程导航算法村第七关 |二叉树的遍历

编程导航算法村第七关 | 二叉树的遍历

前序遍历（递归）

 public List<Integer> preorderTraversal(TreeNode root) {ArrayList<Integer> result = new ArrayList<Integer>();preorder(root, result);return result;}public void preorder(TreeNode root, List<Integer> result) {if (root == null) {return;}result.add(root.val);preorder(root.left, result);preorder(root.right, result);}

前序遍历（迭代）

• 先迭代到树的最底层，左左端的元素，然后弹出栈，访问他的右节点

 public List<Integer> preorderTraversal(TreeNode root) {ArrayList<Integer> result = new ArrayList<Integer>();if (result == null) {return result;}Stack<TreeNode> stack = new Stack<TreeNode>();TreeNode node = root;while (!stack.isEmpty() || node != null) {while (node!= null) {result.add(node.val);stack.push(node);node = node.left;}node = stack.pop();node = node.right;}return result;}

中序遍历（迭代）

 public List<Integer> inorderTraversal(TreeNode root) {ArrayList<Integer> result = new ArrayList<>();if (root == null) {return result;}Stack<TreeNode> stack = new Stack<TreeNode>();TreeNode node = root;while (!stack.isEmpty() || node != null) {while (node != null) {stack.push(node);node = node.left;}node = stack.pop();result.add(node.val);node = node.right;}return result;}

后续遍历（反转法）

• 后续遍历相当于在前序遍历的基础上，先访问右节点再访问左节点，最后翻转

 public List<Integer> postorderTraversal(TreeNode root) {ArrayList<Integer> result = new ArrayList<>();if (root == null) {return result;}Stack<TreeNode> stack = new Stack<TreeNode>();TreeNode node = root;while (!stack.isEmpty() || node != null) {while (node != null) {stack.push(node);result.add(node.val);node = node.right;}node = stack.pop();node = node.left;}Collections.reverse(result);return result;}