二叉树的遍历

文档讲解
视频讲解

递归遍历

递归三要素：

1. 函数的功能（参数、返回值）
2. 边界（递归结束条件）
3. 递推公式（找 f(n) 和 f(n-x) 的关系）

前序遍历

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

    // 1. 函数的功能：遍历当前节点
    public void helper(TreeNode node, List<Integer> res) {
        // 2. 确定边界：节点为空就返回
        if (node == null) return;
        // 3. 递推公式：先处理当前节点，再递归处理其他节点
        res.add(node.val);
        helper(node.left, res);
        helper(node.right, res);
    }
}

中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }

    public void helper(TreeNode node, List<Integer> res) {
        if (node == null) return;
        helper(node.left, res);
        res.add(node.val);
        helper(node.right, res);
    }
}

后序遍历

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

    public void helper(TreeNode node, List<Integer> res) {
        if (node == null) return;
        helper(node.left, res);
        helper(node.right, res);
        res.add(node.val);
    }
}

迭代遍历

前序遍历

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        if (root == null) return res;

        // 先入栈根节点
        stack.push(root);
        while (!stack.isEmpty()) {
            // 访问栈顶节点
            TreeNode node = stack.pop();
            res.add(node.val);
            // 先将右孩子入栈
            if (node.right != null) {
                stack.push(node.right);
            }
            // 再将左孩子入栈
            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return res;
    }

中序遍历

中心思想：

1. 遍历左孩子，依次入栈
2. 访问中间节点（根节点）
3. 遍历右孩子

即有左孩子则将左孩子入栈，否则访问当前节点，然后遍历右孩子。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        // curr 表示当前访问的节点
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                // 左孩子全入栈
                stack.push(curr);
                curr = curr.left;
            } else {
                // 到最底层节点后，访问栈顶元素
                TreeNode top = stack.pop();
                res.add(top.val);
                if (top.right != null) {
                    // 将右孩子作为新起点，开始访问
                    curr = top.right;
                }
            }
        }

        return res;
    }
}

后序遍历

// 迭代之倒反天罡法
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> st = new Stack<>();

        // 访问顺序：根右左
        if (root == null) return res;
        st.push(root);
        while (!st.isEmpty()) {
            TreeNode top = st.pop();
            res.add(top.val);
            if (top.left != null) {
                st.push(top.left);
            }
            if (top.right != null) {
                st.push(top.right);
            }
        }

        // 倒反天罡（反转列表）
        // 访问顺序：左右根，即后序遍历顺序
        int i = 0, j = res.size() - 1;
        while (i < j) {
            int tmp = res.get(i);
            res.set(i, res.get(j));
            res.set(j, tmp);
            i++;
            j--;
        }

        return res;
    }

List<Integer> res = new ArrayList<>();
        Stack<TreeNode> st = new Stack<>();

        if (root == null) return res;
        TreeNode curr = root;
        // 记录上一个访问的节点
        TreeNode prev = null;
        while (curr != null || !st.isEmpty()) {
            if (curr != null) {
                st.push(curr);
                curr = curr.left;
            } else {
                TreeNode top = st.peek();
                if (top.right != null) {
                    if (top.right != prev) {
                        // 右孩子没访问过，则开始遍历右孩子
                        curr = top.right;
                    } else {
                        // 右孩子访问过，则 top 出栈并访问
                        // 访问节点
                        res.add(top.val);
                        // 出栈
                        st.pop();
                        // 记录最近访问的节点
                        prev = top;
                    }
                } else {
                    // 没有右孩子，则 top 出栈并访问
                    // 访问节点
                    res.add(top.val);
                    // 出栈
                    st.pop();
                    // 记录最近访问的节点
                    prev = top;
                }
            }
        }

        return res;