力扣热题-100二叉树专题经典题解析前8道
力扣热题 100：二叉树专题经典题解析（前8道）
在力扣（LeetCode）平台上，二叉树相关的题目是算法面试和练习中的重要部分。今天，我们就来详细解析二叉树专题中的几道经典题目，帮助大家更好地理解解题思路和技巧。
一、二叉树的中序遍历（题目 94）
1. 题目描述
给定一个二叉树，返回其节点值的中序遍历。
2. 示例
示例 1：
输入：
root = [1, null, 2, 3]
输出：
[1, 3, 2]
3. 解题思路
这道题主要考察二叉树的中序遍历。中序遍历的顺序是左子树、根节点、右子树。我们可以使用递归或迭代的方法来实现。这里使用递归方法，因为它更简洁易懂。
4. 代码实现（Java）
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderHelper(root, result);
return result;
}
private void inorderHelper(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
inorderHelper(node.left, result);
result.add(node.val);
inorderHelper(node.right, result);
}
}5. 复杂度分析
- 时间复杂度 ：O(n)，其中 n 是二叉树的节点数。每个节点访问一次。
- 空间复杂度 ：O(n)，递归调用栈的深度在最坏情况下为 O(n)（如退化为链表的二叉树）。
二、二叉树的最大深度（题目 104）
1. 题目描述
给定一个二叉树，求其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
2. 示例
示例 1：
输入：
root = [3, 9, 20, null, null, 15, 7]
输出：
3
3. 解题思路
这道题主要考察二叉树的深度计算。我们可以使用递归的方法，分别计算左右子树的深度，然后取最大值加 1（根节点）。
4. 代码实现（Java）
public class Solution {
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;
}
}5. 复杂度分析
- 时间复杂度 ：O(n)，每个节点访问一次。
- 空间复杂度 ：O(n)，递归调用栈的深度在最坏情况下为 O(n)。
三、翻转二叉树（题目 226）
1. 题目描述
翻转一棵二叉树，即将左子树和右子树交换。
2. 示例
示例 1：
输入：
root = [4, 2, 7, 1, 3, 6, 9]
输出：
[4, 7, 2, 9, 6, 3, 1]
3. 解题思路
这道题主要考察二叉树的翻转操作。我们可以使用递归的方法，对每个节点交换其左右子树。
4. 代码实现（Java）
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
}
}5. 复杂度分析
- 时间复杂度 ：O(n)，每个节点访问一次。
- 空间复杂度 ：O(n)，递归调用栈的深度在最坏情况下为 O(n)。
四、对称二叉树（题目 101）
1. 题目描述
给定一个二叉树，判断它是否是镜像对称的。
2. 示例
示例 1：
输入：
root = [1, 2, 2, 3, 4, 4, 3]
输出：
true
3. 解题思路
这道题主要考察二叉树的对称性判断。我们可以使用递归的方法，判断左子树和右子树是否镜像对称。
4. 代码实现（Java）
public class Solution {
public boolean isSymmetric(TreeNode root) {
return isMirror(root, root);
}
private boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return true;
}
if (t1 == null || t2 == null) {
return false;
}
return t1.val == t2.val && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
}
}5. 复杂度分析
- 时间复杂度 ：O(n)，每个节点访问一次。
- 空间复杂度 ：O(n)，递归调用栈的深度在最坏情况下为 O(n)。
五、二叉树的直径（题目 543）
1. 题目描述
给定一个二叉树，求其直径。直径是指任意两个节点之间的最长路径的长度。
2. 示例
示例 1：
输入：
root = [1, 2, 3, 4, 5]
输出：
3
解释：最长路径是 4 → 2 → 1 → 3，长度为 3。
3. 解题思路
这道题主要考察二叉树直径的计算。直径等于左右子树深度之和的最大值。我们可以使用递归的方法，在计算深度的同时更新最大直径。
4. 代码实现（Java）
public class Solution {
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return maxDiameter;
}
private int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
return Math.max(leftDepth, rightDepth) + 1;
}
}5. 复杂度分析
- 时间复杂度 ：O(n)，每个节点访问一次。
- 空间复杂度 ：O(n)，递归调用栈的深度在最坏情况下为 O(n)。
六、二叉树的层序遍历（题目 102）
1. 题目描述
给定一个二叉树，返回其层序遍历的结果。
2. 示例
示例 1：
输入：
root = [3, 9, 20, null, null, 15, 7]
输出：
[[3], [9, 20], [15, 7]]
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<List<Integer>> levelOrder(TreeNode root) {
List<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();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < levelSize; 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);
}
}
result.add(level);
}
return result;
}
}5. 复杂度分析
- 时间复杂度 ：O(n)，每个节点访问一次。
- 空间复杂度 ：O(n)，队列在最坏情况下存储一层的所有节点。
七、将有序数组转换为二叉搜索树（题目 108）
1. 题目描述
给定一个升序排列的数组，将其转换为高度平衡的二叉搜索树。
2. 示例
示例 1：
输入：
nums = [-10, -3, 0, 5, 9]
输出：
[0, -3, 9, -10, null, 5]
解释：一种可能的平衡二叉搜索树如下：
0
/ \
-3 9
/ /
-10 53. 解题思路
这道题主要考察二叉搜索树的构建。我们可以使用递归的方法，选择数组的中间元素作为根节点，然后递归构建左右子树。
4. 代码实现（Java）
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
private TreeNode helper(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
return root;
}
}5. 复杂度分析
- 时间复杂度 ：O(n)，每个元素访问一次。
- 空间复杂度 ：O(log n)，递归调用栈的深度在平衡情况下为 O(log n)。
八、验证二叉搜索树（题目 98）
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)。
以上就是力扣热题 100 中与二叉树相关的经典题目的详细解析，希望对大家有所帮助。在实际刷题过程中，建议大家多动手实践，理解解题思路的本质，这样才能更好地应对各种算法问题。
