【算法总结】你真的掌握了二叉树的遍历嘛

喜欢ヅ旅行 2022-11-19 09:54 171阅读 0赞

## 前言 ##

说到树的四种遍历方式，可能大家第一时间都会想到它的四种遍历方式，并快速说了它的特点。

1.  先序(先根)遍历：即先访问根节点，再访问左孩子和右孩子
2.  中序遍历：先访问做孩子，再访问根节点和右孩子
3.  后序遍历：先访问左孩子，再访问右孩子，再访问根节点
4.  层次遍历：按照所在层数，从下往上遍历

接着当你要手动写代码的时候，你写得出来嘛？

1.  递归实现二叉树的前序，中序，后续遍历
2.  非递归二叉树的实现前序，中序，后续遍历
3.  实现二叉树的层序遍历

今天，就让我们一起来看看，怎样实现它？算法这种东东，好记性不如敲键盘。

## 前中后序遍历 ##

假如有以下树

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}

## 小结 ##

1.  递归实现二叉树的前中后遍历，这种方式非常简单，大家一定要掌握
2.  非递归的方式，其实也不难，前中后序遍历方式主要借助栈的特征，层序遍历的方式主要借助队列的方式，大家也要掌握，多敲两遍，就记住了。
3.  github 代码地址：https://github.com/gdutxiaoxu/Android\_interview/

## 往期文章 ##

[面试官：简历上最好不要写Glide，不是问源码那么简单][Glide]

[常见的链表翻转，字节跳动加了个条件，面试者高呼「我太难了」| 图解算法][Link 1]

[面试官，怎样实现 Router 框架？][Router]

[java 版剑指offer集锦][java _offer]

[面试官系列 - LeetCode链表知识点&题型总结][- LeetCode]

[徐公自叙][Link 2]

[得屌丝者得天下，米粉≠屌丝][Link 3]

[面试官：手写生产者消费者模型][Link 4]

[【算法总结】五道常见的算法-二叉树][-]

如果你觉得对你有所帮助的话，可以关注我的公众号 程序员徐公（stormjun94)，第一时间会在上面更新

![image][]

[Glide]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95b6acdaed27c375ee10b95434888c98af8aa021dc3db035e0f043e8c2139a81a17cd675f&idx=1&mid=2247484458&scene=21&sn=44712068a160ab7eb234b8109dc1ea0a#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95b64cdaed2723ca5c8fa28ba272a5622da649135f5dfcfb9e1b069bbd1bbd057b52d6445&idx=1&mid=2247484452&scene=21&sn=1bc60c27b6aba442f8aa08f95a031bbe#wechat_redirect
[Router]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95b6ecdaed2782e8c62629cbd880276b53a8099cecf01e62d043344bb70f947316931a540&idx=1&mid=2247484462&scene=21&sn=5dac470d0ad7da6ec763bc8aba9686e2#wechat_redirect
[java _offer]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95a34cdaed322ce765f23030d44191784923a4ce70acc750cc32d8859af16225f89a4662f&idx=2&mid=2247484788&scene=21&sn=7df4d6de80c077d3268e19067c04ef81#wechat_redirect
[- LeetCode]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95ac4cdaed3d2403d605ec09861f6796d082eab05d4f7f6c104d3d3e3f1d17ae4b7d10ecc&idx=1&mid=2247484804&scene=21&sn=d498f9d0e9b3811b26e86694ef66e9ba#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95af1cdaed3e7709433e6fae34b6dbf3389f77800ac91964562b0a1b26aab572fa1b86c48&idx=1&mid=2247484849&scene=21&sn=e77d1bf8d9139a23c58e149e75cc5c4f#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95afecdaed3e83c85b22f28c7b160e5e5ce27bd61f677a574e151e0a61642bd0908a7a924&idx=1&mid=2247484862&scene=21&sn=fabaf0fd11d5aa4b14de1fc4627f5adc#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95aadcdaed3bb707f2ed96306ea5462ea1e9ce20b71b6af158372d53644396998b78416e9&idx=1&mid=2247484909&scene=21&sn=e83b7b0e69fb630c4549ef9b23c79793#wechat_redirect
[-]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95abacdaed3ac69fb2d331020188f7b1c21fac9d7519308395f55e120fb4c6d2be4e0a661&idx=1&mid=2247484922&scene=21&sn=df3dfad24d2caefb788369ba62ad31f4#wechat_redirect
[image]: /images/20221119/83c91db1c7d140b6b062f9dddf49e4d7.png