你总结得非常到位，二叉树的核心算法确实围绕遍历展开，并能演化出各种题型。作为一名iOS开发者，你在理解这些递归和遍历过程时，可以联想到 UIView 的层级树（subviews）的遍历，底层逻辑是相通的。
以下是这9类经典二叉树问题的JavaScript最优解，包含思路、代码和复杂度分析。
1、后序遍历适合“需要先知道子树结果，再处理当前节点”的场景，尤其是涉及到根节点的决策或合并子树信息时
2、
1. 二叉树的层序遍历 (BFS)
题目：给你一个二叉树，返回其节点值的层序遍历结果（即逐层从左到右访问所有节点）。
// 最优解：使用队列进行广度优先搜索
function levelOrder(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;
}
// 时间复杂度 O(n)，空间复杂度 O(n)
工程关联：这与iOS中遍历 UIView 的所有子视图来刷新布局，或RN/Flutter中框架计算渲染树尺寸的过程非常相似。
2. 二叉树的最大深度
题目：给定一个二叉树，找出其最大深度（从根节点到最远叶子节点的最长路径上的节点数）。
// 最优解：深度优先递归（分治思想）
function maxDepth(root) {
if (root === null) return 0; // 空节点深度为0
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1; // 当前节点深度 = 左右子树最大深度 + 1
}
// 时间复杂度 O(n)，空间复杂度 O(h) [h为树高，递归栈深度]
详细过程讲解
// 假设节点结构为 { val, left, right }
const root = {
val: 3,
left: { val: 9, left: null, right: null },
right: {
val: 20,
left: { val: 15, left: null, right: null },
right: { val: 7, left: null, right: null }
}
};
function maxDepth(root) {
if (root === null) return 0;
const leftDepth = maxDepth(root.left); // 递归计算左子树深度
const rightDepth = maxDepth(root.right); // 递归计算右子树深度
return Math.max(leftDepth, rightDepth) + 1; // 当前节点深度
}
// 递归过程详解（带注释）：
maxDepth(root) // root.val = 3
leftDepth = maxDepth(root.left) // root.left.val = 9
leftDepth = maxDepth(root.left.left) // null => 0
rightDepth = maxDepth(root.left.right) // null => 0
return Math.max(0, 0) + 1 // 1
rightDepth = maxDepth(root.right) // root.right.val = 20
leftDepth = maxDepth(root.right.left) // root.right.left.val = 15
leftDepth = maxDepth(root.right.left.left) // null => 0
rightDepth = maxDepth(root.right.left.right) // null => 0
return Math.max(0, 0) + 1 // 1
rightDepth = maxDepth(root.right.right) // root.right.right.val = 7
leftDepth = maxDepth(root.right.right.left) // null => 0
rightDepth = maxDepth(root.right.right.right) // null => 0
return Math.max(0, 0) + 1 // 1
return Math.max(1, 1) + 1 // 2
return Math.max(1, 2) + 1 // 3
// 最终结果：最大深度为 3
3. 二叉树的最近公共祖先 (LCA)
题目：给定一个二叉树，找到该树中两个指定节点的最近公共祖先。
// 最优解：后序遍历递归
function lowestCommonAncestor(root, p, q) {
// 递归终止条件：遇到空节点或目标节点
if (root === null || root === p || root === q) return root;
// 在左右子树中查找
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
// 情况1：左右子树各找到一个，则当前节点是LCA
if (left && right) return root;
// 情况2：只在左子树找到，则LCA在左子树中
// 情况3：只在右子树找到，则LCA在右子树中
return left ? left : right;
}
// 时间复杂度 O(n)，空间复杂度 O(h)
4. 路径总和
题目：给定一个二叉树和一个目标和，判断该树中是否存在从根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
// 最优解：带状态回溯的深度优先搜索
function hasPathSum(root, targetSum) {
if (root === null) return false;
// 到达叶子节点时判断
if (root.left === null && root.right === null) {
return root.val === targetSum;
}
// 递归检查左右子树，更新剩余目标和
const remaining = targetSum - root.val;
return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
}
// 时间复杂度 O(n)，空间复杂度 O(h)
5. 二叉树的镜像/翻转
题目：翻转一棵二叉树（即每个节点的左右子树互换）。
// 最优解：递归交换左右子树
function invertTree(root) {
if (root === null) return null;
// 递归翻转左右子树
const left = invertTree(root.left);
const right = invertTree(root.right);
// 交换当前节点的左右子树
root.left = right;
root.right = left;
return root;
}
// 时间复杂度 O(n)，空间复杂度 O(h)
6. 二叉树的序列化与反序列化
题目：设计一个算法来序列化和反序列化二叉树（将二叉树转换为字符串，并且可以将字符串转换回原始的树结构）。
// 最优解：前序遍历递归实现
function serialize(root) {
if (root === null) return '#,'; // 用 # 表示空节点，逗号分隔
// 前序遍历：根 -> 左 -> 右
return root.val + ',' + serialize(root.left) + serialize(root.right);
}
function deserialize(data) {
const nodes = data.split(','); // 分割成数组
function buildTree(arr) {
const val = arr.shift(); // 取出当前节点值
if (val === '#') return null; // 空节点
// 前序遍历顺序构建：根 -> 左 -> 右
const node = new TreeNode(parseInt(val));
node.left = buildTree(arr);
node.right = buildTree(arr);
return node;
}
return buildTree(nodes);
}
// 时间复杂度 O(n)，空间复杂度 O(n)
7. 二叉树的直径
题目：给定一棵二叉树，你需要计算它的直径长度（一棵二叉树的直径长度是任意两个结点路径长度中的最大值，这条路径可能穿过也可能不穿过根结点）。
// 最优解：深度优先遍历，在计算深度的同时更新直径
function diameterOfBinaryTree(root) {
let maxDiameter = 0;
// 递归计算节点深度
function depth(node) {
if (node === null) return 0;
const leftDepth = depth(node.left);
const rightDepth = depth(node.right);
// 更新最大直径：左子树深度 + 右子树深度
maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
// 返回当前节点的深度
return Math.max(leftDepth, rightDepth) + 1;
}
depth(root);
return maxDiameter;
}
// 时间复杂度 O(n)，空间复杂度 O(h)
8. 二叉树的右视图
题目：给定一个二叉树的根节点，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
// 最优解：层序遍历取每层最后一个节点
function rightSideView(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length) {
const levelSize = queue.length;
let lastNode = null;
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
lastNode = node.val; // 不断更新为本层最后一个节点的值
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(lastNode); // 添加本层最后一个节点的值
}
return result;
}
// 时间复杂度 O(n)，空间复杂度 O(n)
9. 判断平衡二叉树
题目：给定一个二叉树，判断它是否是高度平衡的二叉树（一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1）。
// 最优解：自底向上递归，避免重复计算
function isBalanced(root) {
function checkHeight(node) {
if (node === null) return 0; // 空节点高度为0
// 检查左子树是否平衡，并获取高度
const leftHeight = checkHeight(node.left);
if (leftHeight === -1) return -1; // 左子树不平衡
// 检查右子树是否平衡，并获取高度
const rightHeight = checkHeight(node.right);
if (rightHeight === -1) return -1; // 右子树不平衡
// 检查当前节点是否平衡
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1; // 不平衡
}
// 返回当前节点的高度
return Math.max(leftHeight, rightHeight) + 1;
}
return checkHeight(root) !== -1;
}
// 时间复杂度 O(n)，空间复杂度 O(h)
10. 判断对称二叉树
题目：给定一个二叉树，检查它是否是镜像对称的。
// 最优解：递归比较两棵子树是否对称
function isSymmetric(root) {
if (root === null) return true;
// 比较左右子树是否对称
function compare(left, right) {
// 都为空
if (left === null && right === null) return true;
// 只有一个为空
if (left === null || right === null) return false;
// 值不相等
if (left.val !== right.val) return false;
// 递归比较：左子树的左 vs 右子树的右，左子树的右 vs 右子树的左
return compare(left.left, right.right) && compare(left.right, right.left);
}
return compare(root.left, root.right);
}
// 时间复杂度 O(n)，空间复杂度 O(h)
💡 面试要点与你的优势结合
- 复杂度分析：每道题都注明复杂度，面试时主动说明，展示专业度。
- 递归与迭代：理解递归的空间成本（调用栈），在面试中可主动提出：“如果需要优化空间，我可以提供迭代解法。”
-
跨栈视角：当被问到“如何应用”时，你可以关联：
-
最大深度/层序遍历 ↔
UIView的层级深度计算、RN/Flutter 的布局过程 - 序列化 ↔ 本地缓存视图状态、网络传输树形结构数据
- 平衡判断 ↔ 保持数据结构高效查询（如AVL树思想）
-
最大深度/层序遍历 ↔
-
大厂考察重点：字节、腾讯等大厂不仅要求写出代码，更注重：
- 边界条件处理（空树、单节点）
- 代码简洁性（能否用最清晰的逻辑实现）
- 能否优化（如平衡判断从O(n²)优化到O(n)）
