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

系列文章目录

力扣热题 100：哈希专题三道题详细解析(JAVA)
力扣热题 100：双指针专题四道题详细解析(JAVA)
力扣热题 100：滑动窗口专题两道题详细解析（JAVA）
力扣热题 100：子串专题三道题详细解析(JAVA)
力扣热题 100：普通数组专题五道题详细解析(JAVA)
力扣热题 100：矩阵专题四道题详细解析（JAVA）
力扣热题 100：链表专题经典题解析(前7道)
力扣热题 100：链表专题经典题解析（后7道）
力扣热题 100：二叉树专题经典题解析（前8道）
力扣热题 100：二叉树专题进阶题解析（后7道）
力扣热题 100：图论专题经典题解析
力扣热题 100：回溯专题经典题解析
力扣热题 100：二分查找专题经典题解析
力扣热题 100：栈专题经典题解析
力扣热题 100：堆专题经典题解析
力扣热题 100：贪心算法专题经典题解析
力扣热题 100：动态规划专题经典题解析
力扣热题 100：多维动态规划专题经典题解析
力扣热题 100：技巧专题经典题解析

在力扣（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 中与二叉树相关的进阶题目的详细解析，希望对大家有所帮助。在实际刷题过程中，建议大家多动手实践，理解解题思路的本质，这样才能更好地应对各种算法问题。