vlambda博客
学习文章列表

本专题为算法模板专题，为笔试面试的Java同学们提供参考使用。

前序遍历的关键在于：先遍历根节点，再遍历左子树，再遍历右子树。

即：根→左→右

(1) 递归写法

对于递归写法大家肯定都是非常清楚的，因为它的代码很简单，也比较容易理解，如下：

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) return res;
        dfs(root);
        return res;
    }

    public void dfs(TreeNode root){
        if(root == null) return ;
        res.add(root.val);    //先遍历根节点
        dfs(root.left);     //再遍历左子树
        dfs(root.right);    //再遍历右子树
    }
}

(2) 迭代写法

要把递归写法改成迭代写法，需要用到的一个很重要的数据结构：栈，用它来保存我们上一个结点，也就是记录我们从哪里来，这样在处理完某个结点的时候，我们可以通过栈来倒退回上一步，这就是迭代写法的核心。

代码如下：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stk = new Stack<>();
        if(root == null) return res;
        while(root != null || !stk.isEmpty()){
            while(root != null){
                res.add(root.val);    //遍历根节点
                stk.push(root);     //把根节点加入栈中保证我们可以退回到上一步
                root = root.left;    //遍历左子树
            }
            root = stk.pop();    //出循环时root为null，回到上一步（即栈顶元素）
            root = root.right;    //遍历它的右子树
        }
        return res;
    }
}

中序遍历的关键在于：先遍历左子树，再遍历根节点，最后遍历右子树。

即：左→根→右。

(1) 递归写法

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return res;
        dfs(root);
        return res;
    }
    public void dfs(TreeNode root){
        if(root == null) return ;
        dfs(root.left);     //遍历左子树
        res.add(root.val);    //遍历根节点
        dfs(root.right);    //遍历右子树
    }
}

(2) 迭代写法

同样的道理用栈来记录我们的遍历路径，代码与前序遍历十分相似。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stk = new Stack<>();
        if(root == null) return res;
        while(root != null || !stk.isEmpty()){
            while(root != null){
                stk.push(root);     //记录遍历路径
                root = root.left;    //遍历左子树
            }
            root = stk.pop();     //出循环时root为null，回到上一步（即栈顶）
            res.add(root.val);     //遍历根节点
            root = root.right;     //遍历右子树
        }
        return res;
    }
}

对比前序遍历可以发现，其实就是res.add(root.val)这一行代码的位置发生了变化，所以是比较好记忆的。

后序遍历的关键在于：先遍历左子树，再遍历右子树，最后遍历根节点。

即：左→右→根。

(1) 递归写法

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null) return res;
        dfs(root);
        return res;
    }

    public void dfs(TreeNode root){
        if(root == null) return ;
        dfs(root.left);      //遍历左子树
        dfs(root.right);     //遍历右子树
        res.add(root.val);     //遍历根节点
    }
}

(2) 迭代写法

后序遍历的迭代写法稍微有一点不同，需要转换一下思路，如果我们直接去写的话会发现并不好写，所以我们可以观察一下特点。

前序遍历的顺序是：根左右，后序遍历的顺序是：左右根，如果把前序遍历的结果反转一下就是：右左根，与后序遍历的顺序相差在左右子树的遍历顺序上。

所以后序遍历的迭代写法可以在前序遍历的迭代写法上进行小小的修改。

即：先遍历根节点，再遍历右子树，最后遍历左子树。得到的结果最后反转一下，就是二叉树的后序遍历。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stk = new Stack<>();
        if(root == null) return res;
        while(root != null ||!stk.isEmpty()){
            while(root != null){
                res.add(root.val);     //遍历根节点
                stk.push(root);      //记录遍历路径
                root = root.right;     //遍历右子树
            }
            root = stk.pop();      //出循环时root为null，回到上一步（即栈顶）
            root = root.left;      //遍历左子树
        }
        Collections.reverse(res);     //反转结果
        return res;
    }
}

我们可以发现，其实二叉树的前中后序遍历的迭代写法是非常相似的，我们只需要理解之后就十分容易直接记住。

前序遍历与中序遍历代码的区别只是一行代码的位置发生了改变；

后序遍历是在前序遍历的基础上稍作修改；

所以我们只需要记住三点：

(1) 迭代写法需要用到栈

(2) 循环是while(root != null || !stk.isEmpty())

(3) 前序遍历思路，中序遍历改一行代码位置，后序遍历：根右左，最后把答案反转

二叉树的遍历就是这么简单~

扫描下方二维码，欢迎关注ACJavaBear。 

我是小熊，转行Java的化学僧。

ACJavaBear将会被打造成一个Java仓库。

希望帮助和我一样转行学Java的同学们。