1.二叉树的递归遍历
前序：
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new LinkedList<>(); preorder(root,list); return list; } public void preorder(TreeNode root,List<Integer> list) { if(root == null) return; list.add(root.val); preorder(root.left,list); preorder(root.right,list); } }
后序：
class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new LinkedList<>(); postorder(root,list); return list; } public void postorder(TreeNode root,List<Integer> list) { if(root == null) return; postorder(root.left,list); postorder(root.right,list); list.add(root.val); } }
中序：
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new LinkedList<>(); inorder(root,list); return list; } public void inorder(TreeNode root,List<Integer> list) { if(root == null) return; inorder(root.left,list); list.add(root.val); inorder(root.right,list); } }
思路：
递归实现二叉树遍历还是很简单的。
2.二叉树的迭代遍历
前序：
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new LinkedList<>(); Stack<TreeNode> stack = new Stack<>(); if(root != null) stack.push(root); while(!stack.empty()) { TreeNode node = stack.pop(); list.add(node.val); if(node.right != null) stack.push(node.right); if(node.left != null) stack.push(node.left); } return list; } }
思路：
我们利用入栈结点，然后出栈时将数值存入结果数组，然后要入栈此节点的孩子结点。由于前序遍历：根 左 右
由于栈是先进后出，所以我们要先入栈右结点，后入栈左节点
后序：
class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new LinkedList<>(); Stack<TreeNode> stack = new Stack<>(); if(root != null) stack.push(root); while(!stack.empty()) { TreeNode node = stack.pop(); list.add(node.val); if(node.left != null) stack.push(node.left); if(node.right != null) stack.push(node.right); } Collections.reverse(list); return list; } }
思路：
根据前序遍历的特点：根 左 右
后序遍历的特点： 左 右 根
所以将左 右 入栈的顺序颠倒后，再将结果数组reverse，就完成了后序遍历的迭代
中序：
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null){ return result; } Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()){ if(cur != null) { stack.push(cur); cur = cur.left; }else { cur = stack.pop(); result.add(cur.val); cur = cur.right; } } return result; } }
思路：
中序遍历的迭代与前序后序不同，因为他是左 根 右 ，所以不是遍历到就存储的。
我们用栈存储我们遍历过的结点，用来我们回溯，当cur一直向左直到为null时，我们回溯
将cur指向出栈的结点，然后加入到结果数组，再将cur指向cur.right
直到cur和stack都为空时跳出循环。
