【算法100天 | 7】二叉树的前序、中序、后序、层序遍历（递归和迭代两种实现）

树的遍历

本文聊一下树的两大种（深度优先遍历、广度优先遍历）、四小种（前序遍历、中序遍历、后序遍历、层序遍历）

深度优先遍历

二叉树的深度优先遍历方式有三种：前序遍历、中序遍历、后序遍历。本文主要基于递归算法讨论。

• 前序遍历：遍历顺序为跟节点 --> 左子节点 --> 右子节点
• 中序遍历：遍历顺序为左子节点 --> 跟节点 --> 右子节点
• 后序遍历：遍历顺序为左子节点 --> 右子节点 --> 根节点

1、二叉树前序遍历（LeetCode 144）

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

1）示例

2）思路

按照访问根节点 --> 左子树 --> 右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。整个遍历过程天然具有递归的性质。

3）代码（递归版本）

/**
 * 前序遍历 (LeetCode 144)
 * 方法：递归
 */
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    pre(root, res);
    return res;
}

public static void pre(TreeNode head, List<Integer> list) {
    if (head == null) {
        return;
    }
    list.add(head.val);
    pre(head.left, list);
    pre(head.right, list);
}

4）代码（迭代版本）

用迭代的方式实现递归函数，两种方式本质上是等价的。区别在于递归的时候隐式地维护了一个栈，而迭代则需要显式地将这个栈模拟出来。

/**
 * 前序遍历 (LeetCode 144)
 * 方法：迭代
 */
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode node = root;
    while (!stack.isEmpty() || node != null) {
        while (node != null) {
            res.add(node.val);
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        node = node.right;
    }
    return res;
}

2、二叉树中序遍历（LeetCode 94）

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

1）示例

2）思路

按照访问左子树 --> 根节点 --> 右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。整个遍历过程天然具有递归的性质。

3）代码（递归版本）

/**
 * 中序遍历（LeetCode 94）
 * 方法：递归
 */
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    in(root, res);
    return res;
}

public void in(TreeNode head, List<Integer> list) {
    if (head == null) {
        return;
    }
    in(head.left, list);
    list.add(head.val);
    in(head.right, list);
}

4）代码（迭代版本）

用迭代的方式实现递归函数，两种方式本质上是等价的。区别在于递归的时候隐式地维护了一个栈，而迭代则需要显式地将这个栈模拟出来。

/**
 * 中序遍历 (LeetCode 94)
 * 方法：迭代
 */
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>();
    while (!stack.isEmpty() || root != null) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        res.add(root.val);
        root = root.right;
    }
    return res;
}

3、二叉树的后序遍历（LeetCode 45）

给你一棵二叉树的根节点 root ，返回其节点值的 后序 遍历 。

1）示例

2）思路

按照访问左子树 --> 右子树 --> 根节点的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。整个遍历过程天然具有递归的性质。

3）代码（递归版本）

/**
 * 后序遍历（LeetCode）
 * 方法：递归
 */
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    post(root, res);
    return res;
}

public void post(TreeNode head, List<Integer> list) {
    if (head == null) {
        return;
    }
    post(head.left, list);
    post(head.right, list);
    list.add(head.val);
}

4）代码（迭代版本）

用迭代的方式实现递归函数，两种方式本质上是等价的。区别在于递归的时候隐式地维护了一个栈，而迭代则需要显式地将这个栈模拟出来。

/**
 * 后序遍历 (LeetCode 145)
 * 方法：迭代
 */
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode prev = null;
    TreeNode node = root;
    while (!stack.isEmpty() || node != null) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        // 如果node.right为空，或者已经被遍历过了，则直接将当前节点添加到结果集中。
        if (node.right == null || node.right == prev) {
            res.add(node.val);
            // 更新下 preNode，即：定位住上一个访问节点
            prev = node;
            node = null;
        } else {
            // 入栈的原因: node 节点的 right 不为 null ，并且 node.right 也没有被访问过
            stack.push(node);
            node = node.right;
        }
    }
    return res;
}

深度优先遍历总结

前序遍历、中序遍历、后序遍历的区别在于业务处理的时机，也就是遍历根节点的时机，所以我们可以抽象出一个通用的深度优先遍历函数；

enum OrderType {
    PRE,
    IN,
    POST
}

public void deepOrder(TreeNode head, List<Integer> res, OrderType type) {
    if (head == null) {
        return;
    }
    // 1，业务操作放这里，就是前序
    if (Objects.equals(type, OrderType.PRE)) {
        res.add(head.val);
    }
    deepOrder(head.left, res, type);
    // 2，业务操作放这里，就是中序
    if (Objects.equals(type, OrderType.IN)) {
        res.add(head.val);
    }
    deepOrder(head.right, res, type);
    // 3，业务操作放这里，就是后序
    if (Objects.equals(type, OrderType.POST)) {
        res.add(head.val);
    }
}

广度优先遍历

广度优先遍历是按层层推进的方式，遍历每一层的节点。

4、二叉树的层序遍历（LeetCode 102）

给你二叉树的根节点 root ，返回其节点值的 层序 遍历 。 （即逐层地，从左到右访问所有节点）。

1）示例

2）思路

首先将根节点放入一个队列，然后迭代队列不为空的情况，每次取出队列中当前时间点 的 size个数量的节点，然后遍历这些节点，将这些节点的左子节点、右子节点依次放入到队列中。

3）代码

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        // 只取一层的数据
        int size = queue.size();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode treeNode = queue.poll();
            list.add(treeNode.val);
            if (treeNode.left != null)
                queue.add(treeNode.left);
            if (treeNode.right != null) {
                queue.add(treeNode.right);
            }
        }
        res.add(list);
    }
    return res;
}

5、二叉树的层序遍历 II（LeetCode 107）

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

1）示例

2）思路

这个题和上一题（二叉树的层序遍历（LeetCode 102））基本一模一样，区别在于这题的结果集添加方式为每遍历完一层，就把这一层的数据放在结果期的最前面。

3）代码

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        // 只取一层的数据
        int size = queue.size();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode treeNode = queue.poll();
            list.add(treeNode.val);
            if (treeNode.left != null)
                queue.add(treeNode.left);
            if (treeNode.right != null) {
                queue.add(treeNode.right);
            }
        }
        res.add(0, list);
    }
    return res;
}