112. 路径总和
var hasPathSum = function (root, targetSum) {
// 空树：没有根到叶子的路径，一律 false（与 targetSum 大小无关）
if (root === null) return false;
// 叶子节点：真正的判定点——拿"剩余目标和"与叶子自身值比较
if (root.left === null && root.right === null) {
return targetSum === root.val;
}
// 非叶子：减去当前值后向左右子树委托，任一边命中即"存在"
const remaining = targetSum - root.val;
return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
};复杂度：时间 O(n)，每个节点至多访问一次（|| 短路命中后不再遍历右子树）；空间 O(H)，H 为树高（递归栈深度），链状树最坏 O(n)。
关键套路：判定型 DFS——只有两个出口：空节点返回 false（“没有路径”），叶子节点返回 targetSum === root.val；中间节点只做减法向下委托。因为节点值可为负，中途 剩余 < 0 不能剪枝，这也是它不需要 437 那套前缀和的原因。
易错点：
- 空树返回
false，不是targetSum === 0——“没有路径” ≠ “有路径但和为 0” - 只有叶子才能下结论：
[1,2], targetSum=1中根 1 非叶子，即使1-1=0也必须继续走到 2 Node.val范围 -1000~1000，和可能先增后减，负值剪枝全是 bug
关联：
129. 求根节点到叶节点数字之和
var sumNumbers = function (root) {
const res = [];
const path = [];
const dfs = (node) => {
if (!node) return;
path.push(node.val);
// 叶子：根到叶路径完整，记录快照（防止后续回溯污染）
if (node.left === null && node.right === null) {
res.push([...path]);
}
dfs(node.left);
dfs(node.right);
// 回溯：每个节点离开时撤销自己，叶子/非叶子统一生效
path.pop();
};
dfs(root);
return res.map((a) => +a.join('')).reduce((a, b) => a + b);
};复杂度：时间 O(n)，每个节点进出 path 各一次（+ 末尾按路径拼接数字的 O(n·H)）；空间 O(H) 为 path/递归栈，res 输出最坏 O(n·H)，链状树退化 O(n²)。
关键套路：回溯型 DFS 收集所有根到叶路径——push 在进入节点时、pop 在离开节点时，进出配对，叶子处记录 [...path] 快照。这是 112. 路径总和（判定型）之后向”枚举型”的进阶。
易错点：
- 判空用
=== null不是=== undefined（LeetCode 树的空子节点是 null） - pop 必须对非叶子节点也生效——只在叶子分支 pop，深度 ≥ 3 的树回溯后 path 会残留脏节点
- 空树时
res为空数组，.reduce()无初值抛 TypeError（本题约束节点数 ≥ 1，安全） - 优化方向：不必存路径数组，向下传
cur = cur * 10 + node.val，叶子处累加，空间降到 O(H)
关联：
222. 完全二叉树的节点个数
两种解法
暴力解（任意遍历计数）：前序 / 中序 / 后序 / 层序都行，本质是把每个节点访问一遍计数。时间 O(n)、空间 O(H)。能 AC，但错过这题考点——它特意标了「完全二叉树」。
优化解（利用完全二叉树性质）：O(log²n)，把「满的那半边」整块算掉，只递归不完整的一半。
优化解代码
const getDepth = (node) => {
let deep = 0;
while (node) { // 关键：判 node 本身，不是 node.left（否则 null 会崩 + 少算一层）
deep++;
node = node.left;
}
return deep;
};
var countNodes = function (root) {
if (root === null) return 0;
const lh = getDepth(root.left);
const rh = getDepth(root.right);
if (lh === rh) return Math.pow(2, lh) + countNodes(root.right); // 左满 → 跳左，递归右
else return Math.pow(2, rh) + countNodes(root.left); // 右满 → 跳右，递归左
};
1 << lh等价于Math.pow(2, lh)；但树高 ≥ 31 时1 << lh会溢出变负，故这里用Math.pow更稳。
复杂度：时间 O(log²n)——递归深度 O(log n)（每步只钻不完整的一半），每层两次 getDepth 各 O(log n)；空间 O(log n) 递归栈。对比暴力 O(n)，节点上亿时差距显著。
关键套路：为什么是 ===
完全二叉树 = 除最后一层全满 + 最后一层左对齐。推出三个不变量（对任意节点）：
- 左子树高度
lh≥ 右子树高度rh（左对齐保证） lh与rh只差 0 或 1lh === rh⟺ 左子树满；lh === rh + 1⟺ 右子树满
第 3 条是命门：=== 是唯一精确表达「左子树满」的判据。因为右子树能到达和左子树一样的深度，只有在左边被完全填满时才可能发生——左边但凡缺一个节点，右边就探不到同一层。
⚠️ 为什么不是 >：用 > 会把 lh > rh（左不完整）误判成「左满」，于是用 2^lh 虚增节点算错。反例：根有左孩子 L、右孩子 R，L 只有左孩子 LL（lh=2, rh=1），> 会算出 5 而非正确 4。
可视化样例（4 层非满完全二叉树）
A
/ \
B C
/ \ / \
D E F G
/ \ /
H I J共 10 节点（第 4 层只填了 H、I、J 三个，左对齐 → 完全但不满）。
算法逐步 trace（countNodes 只递归 A→B→E→J 一条链，其余整块跳过）：
| 步骤 | 当前节点 | 左高 lh | 右高 rh | 比较 | 满的一边（整块算掉） | 本步贡献 2^· | 递归去向 | 跳过谁 |
|---|---|---|---|---|---|---|---|---|
| 1 | A | 3（B→D→H） | 2（C→F） | 3 > 2 | 右满（C、F、G） | 2^2 = 4（含 A） | 递归左 → B | 跳过 C 子树 |
| 2 | B | 2（D→H） | 2（E→J） | 2 === 2 | 左满（D、H、I） | 2^2 = 4（含 B） | 递归右 → E | 跳过 D 子树 |
| 3 | E | 1（J） | 0（空） | 1 > 0 | 右满（空） | 2^0 = 1（含 E） | 递归左 → J | 跳过右(空) |
| 4 | J | 0 | 0 | 0 === 0 | 左满（空） | 2^0 = 1（含 J） | 递归右 → null | 结束 |
累加：4 + 4 + 1 + 1 = 10 ✓。朴素前序要对全部 10 个节点进函数，优化版只对 4 个节点做决策。
易错点（踩坑记录）
getDepth必须用while(node)，不是while(node.left)：后者传null时null.left直接抛 TypeError；且少算一层（层数要含起点节点）else分支打包的是「右满」子树，必须用Math.pow(2, rh)，写成lh会翻倍多算(1 << lh)与Math.pow(2, lh)等价，但树高 ≥ 31 时位运算溢出，优先Math.powlh < rh在完全二叉树里永不发生，写<语义错（碰巧能算出对数但优化只剩一半）Node.val是节点值，与「节点个数」无关，别被题面干扰
关联：
236. 二叉树的最近公共祖先
var lowestCommonAncestor = function(root, p, q) {
if(root === q || root === p || !root) {
return root
}
const left = lowestCommonAncestor(root.left, p, q)
const right = lowestCommonAncestor(root.right, p, q)
if(left!==null && right!==null) {
return root
}
return left || right
};