二叉树算法题

1. 基本二叉树遍历

1. 前序遍历（Pre-order Traversal）

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

算法步骤：

1. 访问根节点。
2. 前序遍历左子树。
3. 前序遍历右子树。

public class BinaryTree {
    // 前序遍历 - 递归
    public void preOrderTraverse(TreeNode node) {
        if (node != null) {
            System.out.print(node.value + " ");
            preOrderTraversal(node.left);
            preOrderTraversal(node.right);
        }
    }
}

2. 中序遍历 (In-order Traversal)

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

public class BinaryTree {
    // 中序遍历 - 递归
    public void inOrderTraverse(TreeNode node) {
        if (node != null) {
            inOrderTraversal(node.left);
            System.out.print(node.value + " ");
            inOrderTraversal(node.right);
        }
    }
}

3. 后序遍历 (Post-order Traversal)

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

public class BinaryTree {
    // 后序遍历 - 递归
    public void postOrderTraverse(TreeNode node) {
        if (node != null) {
            postOrderTraversal(node.left);
            postOrderTraversal(node.right);
            System.out.print(node.value + " ");
        }
    }
}

2. 二叉树按层遍历

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[] 

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

1. 递归

1. 相同层次的节点归入同一个数组
2. 传入辅助的level参数决定层次

public class Solution {

    List<List<Integer>> levels = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return levels;
        }
        helper(root, 0);
        return levels;
    }

    private void helper(TreeNode node, int level) {
        if (levels.size() == level) {
            levels.add(new ArrayList<>());
        }
        levels.get(level).add(node.val);
        if (node.left != null) {
            helper(node.left, level + 1);
        }
        if (node.right != null) {
            helper(node.right, level + 1);
        }
    }
}

2. 迭代

1. 特例处理： 当根节点为空，则返回空列表 [] 。
2. 初始化： 打印结果列表 res = [] ，包含根节点的队列 queue = [root] 。
3. BFS 循环： 当队列 queue 为空时跳出。
   1. 新建一个临时列表 tmp ，用于存储当前层打印结果。
   2. 当前层打印循环： 循环次数为当前层节点数（即队列 queue 长度）。
      1. 出队： 队首元素出队，记为 node。
      2. 打印： 将 node.val 添加至 tmp 尾部。
      3. 添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue 。
   3. 将当前层结果 tmp 添加入 res 。

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ret = new ArrayList<>();
    if (root == null) {
        return ret;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        List<Integer> level = new ArrayList<>();
        int currentLevelSize = queue.size();
        for (int i = 1; i <= currentLevelSize; ++i) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        ret.add(level);
    }
    return ret;
}

queue.offer 方法是 Java 中 Queue 接口的一部分，用于将元素插入到队列中。与 add 方法不同的是，offer 方法在无法插入元素时（例如队列已满的情况下）不会抛出异常。