树算法题解题思路与代码分析
1. 树的遍历（基础）
核心解题思路
- 深度优先遍历（DFS）：利用递归或栈实现前序、中序、后序遍历。递归写法简洁，迭代写法需手动管理栈。
- 广度优先遍历（BFS）：利用队列实现层序遍历，可获取每层节点。
经典例题：102. 二叉树的层序遍历
题目：给你二叉树的根节点 root，返回其节点值的层序遍历结果（即逐层地，从左到右访问所有节点）。
javascript
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if (!root) return [];
const result = [];
const queue = [root]; // 队列初始包含根节点
while (queue.length) {
const levelSize = queue.length; // 当前层的节点数
const currentLevel = []; // 存储当前层的节点值
for (let i = 0; i < levelSize; i++) {
const node = queue.shift(); // 出队
currentLevel.push(node.val);
// 将下一层节点入队
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(currentLevel);
}
return result;
};关键点：
- 使用队列进行 BFS，每次处理一层。
- 循环开始时记录当前队列长度，确保只处理当前层的节点。
shift()操作在 JavaScript 中时间复杂度 O(n)，但 LeetCode 数据量下可接受；优化可用索引模拟队列。
经典例题：94. 二叉树的中序遍历（迭代版）
题目：给定一个二叉树的根节点 root，返回它的中序遍历。
javascript
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
const result = [];
const stack = [];
let curr = root;
while (curr || stack.length) {
// 不断将左子树压栈
while (curr) {
stack.push(curr);
curr = curr.left;
}
// 弹出栈顶，访问节点
curr = stack.pop();
result.push(curr.val);
// 转向右子树
curr = curr.right;
}
return result;
};关键点：
- 模拟系统栈的过程：先深入左子树，访问根，再处理右子树。
- 迭代写法避免了递归可能导致的栈溢出。
2. 树的性质与属性
核心解题思路
利用递归计算树的深度、对称性、平衡性等属性。通常定义递归函数返回所需信息，并在后序位置进行汇总。
经典例题：104. 二叉树的最大深度
题目：给定一个二叉树，找出其最大深度。
javascript
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
if (!root) return 0;
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
// 当前节点的深度 = 左右子树最大深度 + 1
return Math.max(leftDepth, rightDepth) + 1;
};关键点：
- 递归终止条件：空节点深度为 0。
- 当前节点深度由子树深度决定，后序位置计算。
经典例题：101. 对称二叉树
题目：给定一个二叉树，检查它是否是镜像对称的。
javascript
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
if (!root) return true;
return isMirror(root.left, root.right);
};
function isMirror(left, right) {
if (!left && !right) return true; // 都为空，对称
if (!left || !right) return false; // 一个为空，不对称
// 节点值相等，且左树的左子树与右树的右子树对称，左树的右子树与右树的左子树对称
return left.val === right.val &&
isMirror(left.left, right.right) &&
isMirror(left.right, right.left);
}关键点：
- 定义辅助函数比较两个节点是否互为镜像。
- 递归比较：外侧对内侧，内侧对外侧。
3. 二叉搜索树（BST）
核心解题思路
二叉搜索树的中序遍历是升序序列。利用这一特性可快速验证 BST、查找第 K 小元素等。此外，可借助上下界递归判断 BST 合法性。
经典例题：98. 验证二叉搜索树
题目：给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树。
javascript
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isValidBST = function(root) {
// 辅助函数，传递当前节点允许的取值范围 (min, max)
function validate(node, min, max) {
if (!node) return true;
// 当前节点值必须在 (min, max) 范围内
if (node.val <= min || node.val >= max) return false;
// 左子树所有节点值必须小于当前节点值，即更新上界为 node.val
// 右子树所有节点值必须大于当前节点值，即更新下界为 node.val
return validate(node.left, min, node.val) &&
validate(node.right, node.val, max);
}
return validate(root, -Infinity, Infinity);
};关键点：
- 不能只比较当前节点与左右子节点的值，因为 BST 要求整棵左子树都小于根，整棵右子树都大于根。
- 利用上下界递归传递约束条件。
经典例题：230. 二叉搜索树中第K小的元素
题目：给定一个二叉搜索树的根节点 root，和一个整数 k，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
javascript
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthSmallest = function(root, k) {
const stack = [];
let curr = root;
let count = 0;
while (curr || stack.length) {
// 中序遍历：左 -> 根 -> 右
while (curr) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
count++;
if (count === k) return curr.val;
curr = curr.right;
}
return -1; // 不会执行
};关键点：
- 利用 BST 中序遍历得到升序序列的特性。
- 当遍历到第 k 个节点时直接返回其值，提前终止。
4. 树的路径与求和
核心解题思路
从根到叶子或任意节点之间的路径和问题，通常用 DFS 回溯解决。记录当前路径和，到达叶子时判断是否满足条件。对于路径总和 III，需要利用前缀和思想。
经典例题：112. 路径总和
题目：给你二叉树的根节点 root 和一个表示目标和的整数 targetSum，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
javascript
/**
* @param {TreeNode} root
* @param {number} targetSum
* @return {boolean}
*/
var hasPathSum = function(root, targetSum) {
if (!root) return false;
// 如果是叶子节点，检查是否等于 targetSum
if (!root.left && !root.right) {
return root.val === targetSum;
}
// 递归检查左右子树，目标和减去当前节点值
return hasPathSum(root.left, targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val);
};关键点：
- 递归过程中不断减去当前节点值，到达叶子时判断是否归零。
- 注意空树的情况。
经典例题：113. 路径总和 II
题目：给你二叉树的根节点 root 和一个整数目标和 targetSum，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
javascript
/**
* @param {TreeNode} root
* @param {number} targetSum
* @return {number[][]}
*/
var pathSum = function(root, targetSum) {
const result = [];
const path = [];
function dfs(node, remaining) {
if (!node) return;
path.push(node.val);
// 到达叶子且剩余值等于当前节点值（即路径和等于 targetSum）
if (!node.left && !node.right && remaining === node.val) {
result.push([...path]); // 拷贝路径
} else {
dfs(node.left, remaining - node.val);
dfs(node.right, remaining - node.val);
}
path.pop(); // 回溯
}
dfs(root, targetSum);
return result;
};关键点：
- 使用回溯法，在递归前将当前节点加入路径，递归后弹出。
- 到达叶子且满足条件时，将当前路径的拷贝加入结果集。
5. 树的构造与序列化
核心解题思路
给定两种遍历序列（如前序+中序）可唯一确定一棵二叉树。递归构建：前序第一个为根，在中序中找到根的位置，分割左右子树，递归构建左右子树。
经典例题：105. 从前序与中序遍历序列构造二叉树
题目：给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
javascript
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function(preorder, inorder) {
// 构建中序遍历值到下标的映射，便于快速定位根的位置
const map = new Map();
for (let i = 0; i < inorder.length; i++) {
map.set(inorder[i], i);
}
function build(preStart, preEnd, inStart, inEnd) {
if (preStart > preEnd) return null;
const rootVal = preorder[preStart];
const root = new TreeNode(rootVal);
const inIndex = map.get(rootVal); // 根在中序中的位置
const leftSize = inIndex - inStart; // 左子树节点数
// 左子树：前序 [preStart+1, preStart+leftSize]，中序 [inStart, inIndex-1]
root.left = build(preStart + 1, preStart + leftSize, inStart, inIndex - 1);
// 右子树：前序 [preStart+leftSize+1, preEnd]，中序 [inIndex+1, inEnd]
root.right = build(preStart + leftSize + 1, preEnd, inIndex + 1, inEnd);
return root;
}
return build(0, preorder.length - 1, 0, inorder.length - 1);
};关键点：
- 利用哈希表快速获取根节点在中序遍历中的位置。
- 确定左右子树的节点数量，从而划分前序遍历数组的区间。
- 递归构建左右子树。
6. 最近公共祖先（LCA）
核心解题思路
递归查找：若当前节点为空或等于 p 或 q，则返回当前节点。否则递归查找左右子树。如果左右子树均找到非空节点，则当前节点为 LCA；否则返回非空的那一侧。
经典例题：236. 二叉树的最近公共祖先
题目：给定一个二叉树，找到该树中两个指定节点的最近公共祖先。
javascript
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
if (!root || root === p || root === q) return root;
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
// 如果左右子树分别找到了 p 和 q，则当前节点是 LCA
if (left && right) return root;
// 否则返回找到的那一侧
return left || right;
};关键点：
- 递归返回值的含义：如果找到了 p 或 q，或者找到了它们的祖先，则返回该节点；否则返回 null。
- 后序遍历位置处理左右子树的结果。
7. 层序遍历变种
核心解题思路
在 BFS 层序遍历的基础上，针对每层记录所需信息（如最后一个节点、最大值、平均值等）。
经典例题：199. 二叉树的右视图
题目：给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
javascript
/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length) {
const levelSize = queue.length;
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
// 如果是当前层的最后一个节点，将其值加入结果
if (i === levelSize - 1) result.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
return result;
};关键点：
- 层序遍历时，记录每层的最后一个节点即可。
- 也可使用 DFS 先右后左，记录每层第一个访问的节点。
8. 其他进阶问题
核心解题思路
这类题目涉及更复杂的树结构或巧妙的算法思想，如前序遍历展开、填充 next 指针、树形 DP 等。
经典例题：114. 二叉树展开为链表
题目：给你二叉树的根节点 root，请你将它展开为一个单链表：展开后的单链表应该同样使用 TreeNode，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null。展开顺序与二叉树的前序遍历顺序相同。
javascript
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var flatten = function(root) {
if (!root) return;
// 后序遍历方式展开
flatten(root.left);
flatten(root.right);
// 暂存右子树
const right = root.right;
// 将左子树移到右边
root.right = root.left;
root.left = null;
// 找到当前右子树的末端，接上原来的右子树
let curr = root;
while (curr.right) {
curr = curr.right;
}
curr.right = right;
};关键点：
- 后序遍历顺序：左子树展开、右子树展开，然后将左子树插入到根和右子树之间。
- 需要找到当前右子树的最后一个节点，以便连接原来的右子树。
总结
以上八个分类基本覆盖了力扣上树相关的主流题型。建议按照以下顺序练习：
- 基础遍历：102. 层序遍历 → 94. 中序遍历
- 树的性质：104. 最大深度 → 101. 对称二叉树
- 二叉搜索树：98. 验证 BST → 230. 第K小元素
- 路径与求和：112. 路径总和 → 113. 路径总和 II
- 构造与序列化：105. 从前序中序构造二叉树
- 最近公共祖先：236. 二叉树的最近公共祖先
- 层序遍历变种：199. 右视图
- 进阶挑战：114. 展开为链表