【算法总结】递归和非递归实现二叉树的先序，中序，后序遍历

我的 CSDN 博客:blog.csdn.net/gdutxiaoxu
我的掘金：juejin.im/user/220747…
github: github.com/gdutxiaoxu/
微信公众号：程序员徐公

前言

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

1. 先序(先根)遍历：即先访问根节点，再访问左孩子和右孩子

2. 中序遍历：先访问做孩子，再访问根节点和右孩子

3. 后序遍历：先访问左孩子，再访问右孩子，再访问根节点

4. 层次遍历：按照所在层数，从下往上遍历

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

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

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

3. 实现二叉树的层序遍历

今天，就让我们一起来看看，怎样实现它？

前中后序遍历

假如有以下树

    1
   /   2   3
 / \   4   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 实现。

前序、中序、后序遍只是在对节点访问的顺序有一点不同，其它都相同。

递归实现前序，中序，后序遍历

① 前序

void dfs(TreeNode root) {
    visit(root);
    dfs(root.left);
    dfs(root.right);
}
复制代码

② 中序

void dfs(TreeNode root) {
    dfs(root.left);
    visit(root);
    dfs(root.right);
复制代码

③ 后序

void dfs(TreeNode root) {
    dfs(root.left);
    dfs(root.right);
    visit(root);
}
复制代码

非递归实现二叉树的先序，中序，后序遍历

非递归实现二叉树的前序遍历

144. Binary Tree Preorder Traversal (Medium)

Leetcode / 力扣：leetcode-cn.com/problems/bi…

class Solution {
    //迭代
    public List preorderTraversal(TreeNode root) {
        List res = new ArrayList();
        Stack stack = new Stack();
        while(root!=null || !stack.empty()){
            while(root!=null){
                res.add(root.val); //先将节点加入结果队列
                stack.push(root);  //不断将该节点左子树入栈
                root = root.left;
            }
            root = stack.pop(); //栈顶节点出栈
            root = root.right; //转向该节点右子树的左子树（下一个循环）
        }
        return res; 
    }

}
复制代码

非递归实现二叉树的中序遍历

94. Binary Tree Inorder Traversal (Medium)

Leetcode / 力扣：leetcode-cn.com/problems/bi…

class Solution {
    //迭代
    public List preorderTraversal(TreeNode root) {
        List res = new ArrayList();
        Stack stack = new Stack();
        while(root!=null || !stack.empty()){
            while(root!=null){
                stack.push(root);  //不断将该节点左子树入栈
                root = root.left;
            }
            root = stack.pop(); //栈顶节点出栈
            res.add(root.val); //将节点加入结果队列
            root = root.right; //转向该节点右子树的左子树（下一个循环）
        }
        return res; 
    } 
}
复制代码

非递归实现二叉树的后序遍历

145. Binary Tree Postorder Traversal (Medium)

Leetcode / 力扣：leetcode-cn.com/problems/bi…

前序遍历为 root -> left -> right，后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left，那么这个顺序就和后序遍历正好相反。

//修改前序遍历代码中，节点写入结果链表的代码：将插入队尾修改为插入队首
//修改前序遍历代码中，每次先查看左节点再查看右节点的逻辑：变为先查看右节点再查看左节点
class Solution {
    public List postorderTraversal(TreeNode root) {
        LinkedList res = new LinkedList();
        Stack stack = new Stack();
        TreeNode pre = null;
        while(root!=null || !stack.empty()){
            while(root!=null){
                res.addFirst(root.val); //插入队首
                stack.push(root);
                root = root.right; //先右后左
            }
            root = stack.pop();
            root = root.left;
        }
        return res; 
    }
}
复制代码

非递归实现二叉树的层序遍历

leetcode：leetcode.com/problems/bi…

class Solution {
    public List> levelOrderBottom(TreeNode root) {
        List> res = new LinkedList();
        Queue queue = new LinkedList();
        if(root == null)
            return res;
        queue.add(root);
        while(!queue.isEmpty()){
            int count = queue.size();
            List temp = new LinkedList();
            for(int i=0; i复制代码

小结

1. 递归实现二叉树的前中后遍历，这种方式非常简单，大家一定要掌握

2. 非递归的方式，其实也不难，前中后序遍历方式主要借助栈的特征，层序遍历的方式主要借助队列的方式，大家也要掌握，多敲两遍，就记住了。

3. github 代码地址：github.com/gdutxiaoxu/…

推荐阅读

Android 启动优化（一） - 有向无环图

Android 启动优化（二） - 拓扑排序的原理以及解题思路

Android 启动优化（三）- AnchorTask 开源了

Android 启动优化（四）- AnchorTask 是怎么实现的

Android 启动优化（五）- AnchorTask 1.0.0 版本正式发布了

Android 启动优化（六）- 深入理解布局优化