AC第七天

Jie2025-04-282025-05-06

1. 二叉树的中序遍历 LeetCode

public class LeetCodeTest {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(1,
                null,
                new TreeNode(2, new TreeNode(3), null)
        );
        System.out.println(inorderTraversal(root));
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root,result);
        return result;
    }

    private void inorder(TreeNode node, List<Integer> result) {
        if (node == null) return;
        inorder(node.left, result);
        result.add(node.val);
        inorder(node.right, result);
    }
}

问题描述

给定一个二叉树，要求返回其节点值的中序遍历结果。中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

解题思路

二叉树的遍历方式是数据结构中的基础知识，主要分为三种：先序遍历、中序遍历和后序遍历。中序遍历的特点是按照节点值的顺序输出，常用于二叉搜索树的排序。

方法一：递归

递归是实现二叉树遍历的经典方法。通过递归函数，依次访问左子树、根节点和右子树。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorder(root, result);
    return result;
}

private void inorder(TreeNode node, List<Integer> result) {
    if (node == null) {
        return;
    }
    inorder(node.left, result); // 访问左子树
    result.add(node.val);       // 访问根节点
    inorder(node.right, result); // 访问右子树
}

方法二：迭代

使用栈模拟递归过程，避免函数调用的开销。迭代方法更适合处理深度较大的树。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current); // 将左子树压入栈
            current = current.left;
        }
        current = stack.pop(); // 弹出栈顶元素
        result.add(current.val); // 访问根节点
        current = current.right; // 转向右子树
    }
    return result;
}

方法三：Morris 遍历

Morris 遍历是一种空间复杂度为 O(1) 的遍历方法，通过修改树的结构实现中序遍历。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    TreeNode current = root;

    while (current != null) {
        if (current.left == null) {
            result.add(current.val); // 访问根节点
            current = current.right; // 转向右子树
        } else {
            TreeNode predecessor = current.left;
            while (predecessor.right != null && predecessor.right != current) {
                predecessor = predecessor.right;
            }
            if (predecessor.right == null) {
                predecessor.right = current; // 建立临时链接
                current = current.left;
            } else {
                predecessor.right = null; // 恢复树结构
                result.add(current.val); // 访问根节点
                current = current.right; // 转向右子树
            }
        }
    }
    return result;
}

总结

递归方法简单易懂，但可能会导致栈溢出。
迭代方法适合大规模数据，避免了递归的局限性。
Morris 遍历在不使用额外空间的情况下完成遍历，但需要修改树的结构。

2. 二叉树的最大深度 LeetCode

public class LeetCodeTest {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(3,
                new TreeNode(9),
                new TreeNode(20, new TreeNode(15), new TreeNode(7))
        );
        System.out.println(maxDepth(root));
    }

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

问题描述

给定一个二叉树，找出其最大深度。最大深度是从根节点到最远叶子节点的最长路径上的节点数。

解题思路

二叉树的最大深度问题可以通过递归或迭代的方法解决。

方法一：递归

递归是解决树问题的常用方法。通过递归函数分别计算左子树和右子树的深度，取两者的最大值并加 1 即为当前节点的深度。(dfs)

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
}

方法二：迭代

使用层序遍历（广度优先搜索bfs）计算树的深度。每遍历一层，深度加 1。

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int depth = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        depth++;
    }
    return depth;
}