```javascript
// 严格套用 BFS 模板
var levelOrder = function (root) {
if (root === null) return [];
const queue = [root];
const res = [];
while (queue.length > 0) {
// 一次处理一层
const size = queue.length;
const level = [];
for (let i = 0; i < size; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
res.push(level);
}
return res;
};
```Medium
```javascript
var zigzagLevelOrder = function(root) {
// 套用 BFS 模板，处理每一层的顺序不同
if (root === null) return [];
const queue = [root];
const res = [];
let isOrderLeft = true; // 标记方向
while (queue.length > 0) {
const size = queue.length;
const level = []; // 使用双端队列思想 (这里简单用数组配合反转)
for (let i = 0; i < size; i++) {
const node = queue.shift();
if (isOrderLeft) {
level.push(node.val);
} else {
level.unshift(node.val); // 倒序就从头插，或者等push完再reverse
}
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
res.push(level);
isOrderLeft = !isOrderLeft;
}
return res;
};
``````javascript
var rightSideView = function(root) {
// 套用 BFS 模板
if (root === null) return [];
const queue = [root];
const res = [];
while (queue.length > 0) {
const size = queue.length;
// 这一层的最后一个元素，就是右视图看到的元素
for (let i = 0; i < size; i++) {
const node = queue.shift();
// 如果是当前层的最后一个节点，放入结果集
if (i === size - 1) {
res.push(node.val);
}
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
return res;
};
``````javascript
var widthOfBinaryTree = function(root) {
// 套用 BFS 模板，但需要给节点编号
// 编号规则：root 为 1，左孩子为 2*i，右孩子为 2*i+1
// 关键点：JS数字如果是大数，会精度丢失，需要用 BigInt
if (root === null) return 0;
// queue 存放 [node, index]
// 初始 index 用 1n (BigInt)
const queue = [[root, 1n]];
let maxWidth = 0;
while (queue.length > 0) {
const size = queue.length;
// 记录当前层的 最左索引 和 最右索引
// 肯定分别是队头和队尾（因为是层序的）
// 但注意：for循环执行完后，queue 里剩下的就是下一层的了，所以要在本层开始前记录，或者在循环中记录
let leftIndex, rightIndex;
// 如果想要方便，可以在循环开始前取头尾
// 队头就是本层最左，队尾是本层最右
if (size > 0) {
leftIndex = queue[0][1];
rightIndex = queue[queue.length - 1][1];
// 计算宽度，并转换为 Number
maxWidth = Math.max(maxWidth, Number(rightIndex - leftIndex + 1n));
}
for (let i = 0; i < size; i++) {
const [node, index] = queue.shift();
if (node.left) queue.push([node.left, index * 2n]);
if (node.right) queue.push([node.right, index * 2n + 1n]);
}
}
return maxWidth;
};
```暂无代码答案，请参考 LeetCode 官方题解
```javascript
var isSymmetric = function(root) {
if(root === null) return true;
// 递归判断两个子树是否互为镜像
const check = (left, right) => {
// 1. Base Case
if (left === null && right === null) return true; // 都为空，对称
if (left === null || right === null) return false; // 一个空一个不空，不对称
// 2. Divide: 判断
// A. 根节点值是否相同
if (left.val !== right.val) return false;
// B. 递归比较：左子树的左 vs 右子树的右，左子树的右 vs 右子树的左
return check(left.left, right.right) && check(left.right, right.left);
}
return check(root.left, root.right);
};
``````javascript
var buildTree = function(preorder, inorder) {
// 套用【分治思维】模板
// 1. Base Case: 序列为空，返回 null
if (preorder.length === 0 || inorder.length === 0) {
return null;
}
// 2. 根节点：前序遍历的第一个元素
const rootVal = preorder[0];
const root = new TreeNode(rootVal);
// 3. 找到根节点在中序遍历中的位置，以此划分左右子树
const index = inorder.indexOf(rootVal);
// 4. Divide: 切割数组，递归构建左右子树
// 左子树的中序：[0, index)
// 左子树的前序：[1, index + 1) (长度要和中序一致)
root.left = buildTree(preorder.slice(1, index + 1), inorder.slice(0, index));
// 右子树的中序：[index + 1, end)
// 右子树的前序：[index + 1, end)
root.right = buildTree(preorder.slice(index + 1), inorder.slice(index + 1));
// 5. Return: 返回构建好的根节点
return root;
};
``````javascript
var lowestCommonAncestor = function (root, p, q) {
// 1. Base Case
// 如果是空，或者找到了 p 或 q，直接返回当前节点
if (root === null || root === p || root === q) {
return root;
}
// 2. Divide
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
// 3. Conquer
// 如果左右都找到了，说明当前节点是 LCA
if (left !== null && right !== null) {
return root;
}
// 否则返回非空的那个（即找到了 p 或 q 的那一边）
return left !== null ? left : right;
};
``````javascript
var maxPathSum = function (root) {
let maxSum = Number.MIN_SAFE_INTEGER;
// 分治函数：计算以当前节点为根的单边最大路径和
const dfs = (node) => {
// 1. Base Case
if (node === null) {
return 0;
}
// 2. Divide: 计算左右子树的单边最大贡献（负数也不选）
const leftGain = Math.max(dfs(node.left), 0);
const rightGain = Math.max(dfs(node.right), 0);
// 3. Conquer(Update Global Max): 更新全局最大路径和（包含当前节点和左右子树）
const currentPathSum = node.val + leftGain + rightGain;
maxSum = Math.max(maxSum, currentPathSum);
// 4. Return: 返回当前节点的最大单边路径和给父节点
return node.val + Math.max(leftGain, rightGain);
}
dfs(root);
return maxSum;
};
```暂无代码答案，请参考 LeetCode 官方题解
暂无代码答案，请参考 LeetCode 官方题解
```javascript
var sumNumbers = function(root) {
// 套用【遍历思维】模板 (Traverse)
// 这里的“全局变量”是 dfs 函数的参数，也可以写在外面
let sum = 0;
const dfs = (node, curNum) => {
// 1. Base Case
if (node === null) return;
// 2. 前序位置：更新当前路径的数字
curNum = curNum * 10 + node.val;
// 3. 判断叶子节点：如果到了叶子，累加结果
if (node.left === null && node.right === null) {
sum += curNum;
return;
}
// 4. 继续遍历左右子树
dfs(node.left, curNum);
dfs(node.right, curNum);
}
dfs(root, 0);
return sum;
};
``````javascript
var isSubStructure = function(A, B) {
// 特殊约定：空树不是子结构
if (!A || !B) return false;
// 1. Base Case: 以当前节点匹配
// 2. Divide: 否则去左子树找，或者去右子树找
return isSame(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
};
const isSame = (A, B) => {
// 关键点：B 匹配完了，说明找到了，返回 true
if (!B) return true;
// B 没完但 A 完了，说明匹配不上，返回 false
if (!A) return false;
// 值不同，匹配失败
if (A.val !== B.val) return false;
// 必须左右同时匹配
return isSame(A.left, B.left) && isSame(A.right, B.right);
}
``````javascript
var isValidBST = function (root) {
// 利用 BST 性质：中序遍历是有序的
let pre = -Infinity;
// 返回值：是否合法
const dfs = (node) => {
if (node === null) return true;
// 左
if (!dfs(node.left)) return false;
// 根 (检查是否大于前一个值)
if (node.val <= pre) return false;
pre = node.val;
// 右
return dfs(node.right);
}
return dfs(root);
};
```