【遍历】非递归法 二叉树的前中后序遍历

非递归法

通过栈Stack来模拟递归。

前序遍历

LeetCode 144

前序遍历：1 2 3

定义：存放答案的List、栈Stack

1. 将root入栈
2. 出栈：node，为null则舍弃
3. 将node放入list
4. 将node.right入栈
5. 将node.left入栈
6. 栈不为空则重复2-5步

为了让左节点优先于右节点出栈，因此先将右节点入栈。

class Solution {public List<Integer> preorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> list = new LinkedList<>();stack.push(root);while(!stack.empty()){TreeNode node = stack.pop();if(node==null)continue;list.add(node.val);stack.push(node.right);stack.push(node.left);}return list;}
}

后序遍历

LeetCode 145

后序遍历：2 3 1

后序遍历仅需在前序遍历的代码中修改3处即可。

由前序遍历1 2 3 改为 1 3 2 再翻转为 2 3 1即为答案。

class Solution {public List<Integer> postorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> list = new LinkedList<>();stack.push(root);while(!stack.empty()){TreeNode node = stack.pop();if(node == null)continue;list.add(node.val);stack.push(node.left); // 先放入左节点stack.push(node.right); }Collections.reverse(list); // 反转return list;}
}

中序遍历

LeetCode 94

中序遍历代码与前序和后续不同。

中序遍历： 4 2 5 1 3。

思考：要想先输出4，则需要将左节点持续入栈，直到为null，此时出栈即为4，然后将其右节点入栈…

同样的，定义存放结果的list和栈stack。

1. cur = root
2. cur不为空或者栈不为空
3. 循环 将cur入栈，并将cur赋值其左节点，直到为空
4. 出站node，将node加入list
5. 将node赋值为node.left
6. 重复2 - 5步

class Solution {public List<Integer> inorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> list = new LinkedList<>();TreeNode cur = root;while(cur!=null||!stack.empty()){while(cur!=null){stack.push(cur);cur = cur.left;}TreeNode node = stack.pop(); list.add(node.val);cur = node.right;}return list;}
}

递归法DFS

class Solution {List<Integer> list1 = new LinkedList<>(); // 前序List<Integer> list2 = new LinkedList<>(); // 中序List<Integer> list3 = new LinkedList<>(); // 后序public List<Integer> inorderTraversal(TreeNode root) {traverse(root);return list2; }void traverse(TreeNode root){if(root==null)return;list1.add(root.val); traverse(root.left); // 递归左节点list2.add(root.val);traverse(root.right); // 递归右节点list3.add(root.val);}}

参考：

• cyc2018
• 代码随想录 B站