二叉树的遍历

前序遍历 preorder：根左右中序遍历 inorder：左根右后序遍历 postorder：左右根 每一种遍历都有递归和循环两种方法，其中递归比循环简单得多。 三种遍历递归方法的区别就是递归函数中递归左孩子、右孩子与当前节点的顺序。 而循环则需借用栈来实现。

前序遍历

递归

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); helper(result,root); return result; } public void helper(List<Integer> list,TreeNode node){ if(node == null) return; //根左右 list.add(node.val); helper(list,node.left); helper(list,node.right); } }

---

循环

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); if(root == null) return result; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while(!stack.isEmpty()){ TreeNode node = stack.pop(); result.add(node.val); if(node.right!=null){ stack.push(node.right); } if(node.left!=null){ stack.push(node.left); } } return result; } }

中序遍历

递归

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); helper(result,root); return result; } public void helper(List<Integer> list,TreeNode node){ if(node == null) return; //左根右 helper(list,node.left); list.add(node.val); helper(list,node.right); } }

---

循环

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); 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; } }

后序遍历

递归

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); helper(result,root); return result; } public void helper(List<Integer> list,TreeNode node){ if(node == null) return; //左右根 helper(list,node.left); helper(list,node.right); list.add(node.val); } }

---

循环

用prev表示上一次遍历到的节点，curr是当前遍历的节点，需根据二者的关系来确定接下来的遍历方向。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); if(root == null) return; TreeNode prev = null; TreeNode curr = root; stack.push(root); while(!stack.isEmpty()){ curr = stack.peek(); if(prev == null || prev.left == curr || prev.right == curr){ // traverse down the tree if(curr.left !=null){ stack.push(curr.left); }else if(curr.right != null){ stack.push(curr.right); } }else if(curr.left == prev){ // traverse up the tree from the left if(curr.right != null){ stack.push(curr.right); } }else{ // traverse up the tree from the right result.add(curr.val); stack.pop(); } prev = curr; } return result; } }