前序遍历
思路
- 对于前序来说，遍历的时候访问顺序是：
中 - 左 - 右 - 我们在进行迭代的时候，利用的是
Stack(先进后出)这种数据结构 - 我们遍历的顺序如下图所示：
- 因为我们的出栈顺序为：
左 右，所以压栈的顺序为：右 左
题目代码
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); if(root == null){ return list; } stack.add(root); // 中左右 // 压栈：右左 while(!stack.isEmpty()){ TreeNode node = stack.pop(); list.add(node.val); if(node.right != null){ stack.add(node.right); } if(node.left != null){ stack.add(node.left); } } return list; } }
中序遍历
思路
- 对于中序遍历来说，我们遍历的顺序是：
左 - 中 - 右 - 我们使用的数据结构还是
Stack - 我们遍历的顺序如下图所示：
- 终止而言，对于这种递归的操作，
不要去思考全局，要做好当前的操作，再去递归。
题目代码
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); if(root == null){ return list; } while(!stack.isEmpty() || root != null){ while(root != null){ stack.add(root); root = root.left; } TreeNode node = stack.pop(); list.add(node.val); root = node.right; } return list; } }
后序遍历
思考
- 对于后序遍历，遍历的顺序是：
左 - 右 - 中，而前序遍历为：中 - 左 - 右 - 我们只需要在前序遍历的代码改一下
- 我们可以思考一下，前序中为什么会有
先添加 root.right 再添加 root.left的操作？
- 主要就是在
Stack弹出的时候，按照这个添加顺序，会优先弹出我们的root.left再弹出我们的root.right，达到中 - 左 - 右的顺序 - 我们假如换一下添加的顺序，比如：
先添加 root.left 再添加 root.right，这样的话，弹出的时候，就会按照中 - 右 - 左的顺序 - 可能这时候你还没看出来蹊跷，假如把这个顺序翻转一下，得到
左 - 右 - 后 - 这是不是就是我们的后序遍历了
题目代码
class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); if(root == null){ return list; } stack.add(root); while(!stack.isEmpty()){ TreeNode node = stack.pop(); list.add(node.val); if(node.left != null){ stack.add(node.left); } if(node.right != null){ stack.add(node.right); } } Collections.reverse(list); return list; } }
