力扣热题 100：二叉树专题进阶题解析（后7道）

在力扣（LeetCode）平台上，二叉树相关的题目是算法面试和练习中的重要部分。今天，我们就来详细解析二叉树专题中的几道进阶题目，帮助大家更好地理解解题思路和技巧。

一、验证二叉搜索树（这道在上一篇讲过）

1. 题目描述

给定一个二叉树，判断它是否是有效的二叉搜索树。

2. 示例

示例 1：

输入：root = [2, 1, 3]

输出：true

示例 2：

输入：root = [5, 1, 4, null, null, 3, 6]

输出：false

解释：右子树的根节点 4 小于根节点 5。

3. 解题思路

这道题主要考察二叉搜索树的验证。二叉搜索树的性质是：左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值。我们可以使用递归的方法，同时传递当前节点的合法取值范围。

4. 代码实现（Java）

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }

    private boolean isValidBST(TreeNode node, Integer min, Integer max) {
        if (node == null) {
            return true;
        }
        if ((min != null && node.val <= min) || (max != null && node.val >= max)) {
            return false;
        }
        return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，每个节点访问一次。
• 空间复杂度 ：O(n)，递归调用栈的深度在最坏情况下为 O(n)。

二、二叉搜索树中第 K 小的元素（题目 230）

1. 题目描述

给定一个非空的二叉搜索树和一个整数 k，找到其中第 k 小的元素。

2. 示例

示例 1：

输入：root = [3, 1, 4, null, 2], k = 1

输出：1

3. 解题思路

这道题主要考察二叉搜索树的中序遍历。二叉搜索树的中序遍历结果是升序排列的。我们可以进行中序遍历，并在遍历过程中记录第 k 小的元素。

4. 代码实现（Java）

public class Solution {
    private int count = 0;
    private int result = 0;

    public int kthSmallest(TreeNode root, int k) {
        inorderTraversal(root, k);
        return result;
    }

    private void inorderTraversal(TreeNode node, int k) {
        if (node == null) {
            return;
        }
        inorderTraversal(node.left, k);
        count++;
        if (count == k) {
            result = node.val;
            return;
        }
        inorderTraversal(node.right, k);
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，每个节点访问一次。
• 空间复杂度 ：O(n)，递归调用栈的深度在最坏情况下为 O(n)。

三、二叉树的右视图（题目 199）

1. 题目描述

给定一个二叉树，返回其右视图，即从右侧看所能看到的节点值。

2. 示例

示例 1：

输入：root = [1, 2, 3, null, 5, null, 4]

输出：[1, 3, 4]

解释：二叉树的右视图是 [1, 3, 4]。

3. 解题思路

这道题主要考察二叉树的层序遍历。我们可以使用广度优先搜索（BFS）的方法，按层处理节点，并记录每层的最后一个节点。

4. 代码实现（Java）

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (i == levelSize - 1) {
                    result.add(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return result;
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，每个节点访问一次。
• 空间复杂度 ：O(n)，队列在最坏情况下存储一层的所有节点。

四、二叉树展开为链表（题目 114）

1. 题目描述

给定一个二叉树，将其展开为一个单链表，要求原地修改。

2. 示例

示例 1：

输入：root = [1, 2, 5, 3, 4, null, 6]

输出：[1, null, 2, null, 3, null, 4, null, 5, null, 6]

3. 解题思路

这道题主要考察二叉树的前序遍历。我们可以使用递归的方法，将右子树暂存，然后将左子树移动到右子树的位置，最后将暂存的右子树接到新的右子树的末尾。

4. 代码实现（Java）

public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.left);
        flatten(root.right);
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.left = null;
        root.right = left;
        TreeNode current = root;
        while (current.right != null) {
            current = current.right;
        }
        current.right = right;
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，每个节点访问一次。
• 空间复杂度 ：O(n)，递归调用栈的深度在最坏情况下为 O(n)。

五、从前序与中序遍历序列构造二叉树（题目 105）

1. 题目描述

给定一个二叉树的前序遍历和中序遍历序列，构造该二叉树。

2. 示例

示例 1：

输入：preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]

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

3. 解题思路

这道题主要考察二叉树的构造。前序遍历的第一个元素是根节点，在中序遍历中找到该根节点的位置，左边是左子树，右边是右子树。我们可以使用递归的方法，分别构造左右子树。

4. 代码实现（Java）

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        int index = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) {
                index = i;
                break;
            }
        }
        root.left = buildTree(preorder, preStart + 1, preStart + index - inStart, inorder, inStart, index - 1);
        root.right = buildTree(preorder, preStart + index - inStart + 1, preEnd, inorder, index + 1, inEnd);
        return root;
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，每个节点访问一次。
• 空间复杂度 ：O(n)，递归调用栈的深度在最坏情况下为 O(n)。

六、路径总和 III（题目 437）

1. 题目描述

给定一个二叉树和一个目标值 sum，找到所有从根节点到叶子节点的路径，使得路径上的节点值之和等于 sum。

2. 示例

示例 1：

输入：root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1], sum = 22

输出：[[5, 4, 11, 2], [5, 8, 4, 5]]

3. 解题思路

这道题主要考察二叉树的路径和计算。我们可以使用深度优先搜索（DFS）的方法，递归遍历每个节点，并记录当前路径和路径和。

4. 代码实现（Java）

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(root, sum, path, result);
        return result;
    }

    private void dfs(TreeNode node, int sum, List<Integer> path, List<List<Integer>> result) {
        if (node == null) {
            return;
        }
        path.add(node.val);
        sum -= node.val;
        if (node.left == null && node.right == null && sum == 0) {
            result.add(new ArrayList<>(path));
        }
        dfs(node.left, sum, path, result);
        dfs(node.right, sum, path, result);
        path.remove(path.size() - 1);
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，每个节点访问一次。
• 空间复杂度 ：O(n)，递归调用栈的深度在最坏情况下为 O(n)。

七、二叉树的最近公共祖先（题目 236）

1. 题目描述

给定一个二叉树，找到两个指定节点的最近公共祖先。

2. 示例

示例 1：

输入：root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1

输出：3

解释：节点 5 和节点 1 的最近公共祖先是 3。

3. 解题思路

这道题主要考察二叉树的最近公共祖先的查找。我们可以使用递归的方法，分别在左右子树中查找两个节点。如果两个节点分别在左右子树中，则当前节点是它们的最近公共祖先。

4. 代码实现（Java）

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        return (left != null) ? left : right;
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，每个节点访问一次。
• 空间复杂度 ：O(n)，递归调用栈的深度在最坏情况下为 O(n)。

八、二叉树中的最大路径和（题目 124）

1. 题目描述

给定一个非空的二叉树，找到其中的最大路径和。路径可以是任意节点到任意节点的路径。

2. 示例

示例 1：

输入：root = [1, 2, 3]

输出：6

解释：最大路径是 2 → 1 → 3，和为 6。

3. 解题思路

这道题主要考察二叉树的最大路径和计算。我们可以使用递归的方法，计算每个节点的最大贡献值（即该节点值加上左右子树的最大贡献值），并更新全局最大路径和。

4. 代码实现（Java）

public class Solution {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);
        int priceNewpath = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, priceNewpath);
        return node.val + Math.max(leftGain, rightGain);
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，每个节点访问一次。
• 空间复杂度 ：O(n)，递归调用栈的深度在最坏情况下为 O(n)。

以上就是力扣热题 100 中与二叉树相关的进阶题目的详细解析，希望对大家有所帮助。在实际刷题过程中，建议大家多动手实践，理解解题思路的本质，这样才能更好地应对各种算法问题。