【算法总结】你真的掌握了二叉树的遍历嘛
前言
说到树的四种遍历方式，可能大家第一时间都会想到它的四种遍历方式，并快速说了它的特点。
- 先序(先根)遍历：即先访问根节点，再访问左孩子和右孩子
- 中序遍历：先访问做孩子，再访问根节点和右孩子
- 后序遍历：先访问左孩子，再访问右孩子，再访问根节点
- 层次遍历：按照所在层数，从下往上遍历
接着当你要手动写代码的时候，你写得出来嘛？
- 递归实现二叉树的前序，中序，后续遍历
- 非递归二叉树的实现前序，中序，后续遍历
- 实现二叉树的层序遍历
今天，就让我们一起来看看，怎样实现它？算法这种东东，好记性不如敲键盘。
前中后序遍历
假如有以下树
1 1
2 / \
3 2 3
4 / \ \
54 5 6它的前中后续遍历分别如下
- 层次遍历顺序：[1 2 3 4 5 6]
- 前序遍历顺序：[1 2 4 5 3 6]
- 中序遍历顺序：[4 2 5 1 3 6]
- 后序遍历顺序：[4 5 2 6 3 1]
层次遍历使用 BFS 实现，利用的就是 BFS 一层一层遍历的特性；而前序、中序、后序遍历利用了 DFS 实现。
前序、中序、后序遍只是在对节点访问的顺序有一点不同，其它都相同。
递归实现前序，中序，后序遍历
① 前序
1void dfs(TreeNode root) {
2 visit(root);
3 dfs(root.left);
4 dfs(root.right);
5}② 中序
1void dfs(TreeNode root) {
2 dfs(root.left);
3 visit(root);
4 dfs(root.right);
5}③ 后序
1void dfs(TreeNode root) {
2 dfs(root.left);
3 dfs(root.right);
4 visit(root);
5}1. 非递归实现二叉树的前序遍历
144. Binary Tree Preorder Traversal (Medium)
Leetcode / 力扣：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/description/
1class Solution {
2 //迭代
3 public List<Integer> preorderTraversal(TreeNode root) {
4 List<Integer> res = new ArrayList<Integer>();
5 Stack<TreeNode> stack = new Stack<TreeNode>();
6 while(root!=null || !stack.empty()){
7 while(root!=null){
8 res.add(root.val); //先将节点加入结果队列
9 stack.push(root); //不断将该节点左子树入栈
10 root = root.left;
11 }
12 root = stack.pop(); //栈顶节点出栈
13 root = root.right; //转向该节点右子树的左子树（下一个循环）
14 }
15 return res;
16 }
17
18}2. 非递归实现二叉树的中序遍历
94. Binary Tree Inorder Traversal (Medium)
Leetcode / 力扣：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/description/
1class Solution {
2 //迭代
3 public List<Integer> preorderTraversal(TreeNode root) {
4 List<Integer> res = new ArrayList<Integer>();
5 Stack<TreeNode> stack = new Stack<TreeNode>();
6 while(root!=null || !stack.empty()){
7 while(root!=null){
8 stack.push(root); //不断将该节点左子树入栈
9 root = root.left;
10 }
11 root = stack.pop(); //栈顶节点出栈
12 res.add(root.val); //将节点加入结果队列
13 root = root.right; //转向该节点右子树的左子树（下一个循环）
14 }
15 return res;
16 }
17}3. 非递归实现二叉树的后序遍历
145. Binary Tree Postorder Traversal (Medium)
Leetcode / 力扣：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/description/
前序遍历为 root -> left -> right，后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left，那么这个顺序就和后序遍历正好相反。
1//修改前序遍历代码中，节点写入结果链表的代码：将插入队尾修改为插入队首
2//修改前序遍历代码中，每次先查看左节点再查看右节点的逻辑：变为先查看右节点再查看左节点
3class Solution {
4 public List<Integer> postorderTraversal(TreeNode root) {
5 LinkedList res = new LinkedList();
6 Stack<TreeNode> stack = new Stack<>();
7 TreeNode pre = null;
8 while(root!=null || !stack.empty()){
9 while(root!=null){
10 res.addFirst(root.val); //插入队首
11 stack.push(root);
12 root = root.right; //先右后左
13 }
14 root = stack.pop();
15 root = root.left;
16 }
17 return res;
18 }
19}4. 非递归实现二叉树的层序遍历
leetcode：https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/?spm=a2c4e.10696291.0.0.5e5719a42W3zNP
1class Solution {
2 public List<List<Integer>> levelOrderBottom(TreeNode root) {
3 List<List<Integer>> res = new LinkedList<>();
4 Queue<TreeNode> queue = new LinkedList<>();
5 if(root == null)
6 return res;
7 queue.add(root);
8 while(!queue.isEmpty()){
9 int count = queue.size();
10 List<Integer> temp = new LinkedList<>();
11 for(int i=0; i<count; i++){
12 TreeNode node = queue.poll();
13 temp.add(node.val);
14 if(node.left != null)
15 queue.add(node.left);
16 if(node.right != null)
17 queue.add(node.right);
18 }
19 // 每次都添加到第一个位置
20 res.add(0, temp);
21 }
22 return res;
23 }
24}小结
- 递归实现二叉树的前中后遍历，这种方式非常简单，大家一定要掌握
- 非递归的方式，其实也不难，前中后序遍历方式主要借助栈的特征，层序遍历的方式主要借助队列的方式，大家也要掌握，多敲两遍，就记住了。
- github 代码地址：https://github.com/gdutxiaoxu/Android_interview/