1. 万能递归模版 (DFS - Divide & Conquer)

适用场景：最大深度、直径、最大路径和、翻转二叉树、LCA。
核心心法：后序遍历 (PostOrder)。先递归左右子树拿结果，再汇总当前层。

你做过的「二叉树的直径」和「最大路径和」就是典型。

dfs模版：

 */
var invertTree = function(root) {
    if(!root) return null;

    const dfs = (node) => {
        [node.left, node.right] = [node.right, node.left];

        if(node.left) dfs(node.left);
        if(node.right) dfs(node.right);
    }

    dfs(root);
    return root
};

模版代码 (以求高度为例)：

分治模版：

var maxDepth = function(root) {
    if (!root) return 0; // Base Case

    // 1. 问左右子树要结果 (Divide)
    const left = maxDepth(root.left);
    const right = maxDepth(root.right);

    // 2. 处理当前层逻辑 (Conquer)
    // 比如：我的高度 = max(左, 右) + 1
    return Math.max(left, right) + 1;
};

进阶技巧 (全局变量法)：很多 Hard 题（如最大路径和）的特点是，函数返回给父节点的「单边路径」和题目要求的「全局最大拐弯路径」不一样。
解决方法：设一个全局 maxRes，递归过程中不断更新它，但函数最后 return 给上一层的还是单边值。

2. 层序遍历模版 (BFS - Queue)

适用场景：层序遍历、二叉树右视图、层平均值、最小深度。
核心心法：队列 + size 锁定。用 size 锁死当前层节点数，处理完这一层再进入下一层。

你做过的「二叉树的层序遍历」和「右视图」都是这个。

模版代码：

var levelOrder = function(root) {
    if (!root) return [];
    const queue = [root];
    const res = [];

    while (queue.length) {
        const len = queue.length; // 锁死当前层的节点数
        const currentLevel = [];

        for (let i = 0; i < len; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);

            // 扩展下一层
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        res.push(currentLevel);
    }
    return res;
};

3. BST 中序遍历模版 (Inorder Traversal)

适用场景：验证二叉搜索树、二叉搜索树中第 K 小的元素、将有序数组转为 BST。
核心心法：BST 的中序遍历是有序数组。看到 BST 就条件反射想中序遍历。

你未做的「将有序数组转换为二叉搜索树」其实就是这个模版的逆向操作（二分法构造）。

模版代码 (迭代版，常用于第 K 小 / 验证)：

var isValidBST = function(root) {
    const stack = [];
    let curr = root;
    let prev = -Infinity; // 记录前一个节点的值

    while (curr || stack.length) {
        // 1. 一路向左
        while (curr) {
            stack.push(curr);
            curr = curr.left;
        }

        // 2. 处理当前节点 (中)
        curr = stack.pop();

        // 核心逻辑区域：比如验证是否递增
        if (curr.val <= prev) return false;
        prev = curr.val;

        // 3. 转向右边
        curr = curr.right;
    }
    return true;
};

4. 前缀和模版 (Path Sum Prefix)

适用场景：路径总和 III。
核心心法：二叉树 + Two Sum 的结合体。题目问有多少条路径和为 target，路径不需要从根开始。

暴力双重递归是 O(N^2)。用前缀和 (Map) 可以优化到 O(N)，面试高频考点。

模版代码 (针对“路径总和 III”)：

var pathSum = function(root, targetSum) {
    // key: 前缀和, value: 该前缀和出现的次数
    const map = new Map();
    map.set(0, 1); // 默认前缀和为 0 的有 1 条（啥也不选）
    let count = 0;

    const dfs = (node, curSum) => {
        if (!node) return;

        // 1. 更新当前路径前缀和
        curSum += node.val;

        // 2. 核心公式：找 (curSum - target) 存在过没？
        // 如果存在，说明中间有一段子路径和等于 target
        if (map.has(curSum - targetSum)) {
            count += map.get(curSum - targetSum);
        }

        // 3. 记录当前前缀和，继续递归
        map.set(curSum, (map.get(curSum) || 0) + 1);

        dfs(node.left, curSum);
        dfs(node.right, curSum);

        // 4. 回溯：离开这个节点前，要把这个路径和删掉
        // 因为这只能给子节点用，不能给兄弟节点用
        map.set(curSum, map.get(curSum) - 1);
    };

    dfs(root, 0);
    return count;
};

5. 突击建议

从前序与中序遍历序列构造二叉树：
思路：preorder 第一个是根，拿着这个根去 inorder 里切一刀，左边是左子树，右边是右子树，然后递归。
难点：计算切分后的下标边界。

二叉树展开为链表：
用后序遍历 (Right -> Left -> Root)。
用一个全局变量 prev 记录上一个处理的节点，把当前节点的 right 指向 prev，left 设为 null。

路径总和 III：
直接背诵上面的「前缀和模版」即可。