树形结构的递归

LeetCode 102. 二叉树的层序遍历

一、 核心思路：BFS + 队列 + 分层统计

• 数据结构：使用一个队列（Queue），先进先出，保证按层顺序访问。
• 分层技巧：在每一轮循环开始时，用 let size = queue.length 记录当前层的节点数。这样在后续循环中，只弹出 size 个节点，它们都属于同一层。
• 流程：
  1. 特判：如果 root === null，直接返回空数组。
  2. 初始化结果数组 res = []，将根节点入队 queue = [root]。
  3. while (queue.length > 0)：
     • 记录当前层大小 size = queue.length，创建 level = []。
     • 循环 size 次：从队列头部取出节点，将节点值存入 level，并将该节点的左、右子节点（非空）依次入队。
     • 将 level 推入 res。
  4. 返回 res。

---

二、 完整代码（BFS 迭代写法）

function levelOrder(root) {
    // 边界处理
    if (!root) return [];

    const result = [];
    const queue = [root];

    while (queue.length > 0) {
        // 关键：固定当前层的节点个数
        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)，每个节点恰好被访问一次。
• 空间复杂度：
  • 最坏情况下（完全二叉树最后一层），队列中会存储 n/2 个节点，即 O(n)。
  • 结果数组也占用 O(n)，但通常不计入额外空间（属于输出必需）。

---

四、 进阶写法：递归 DFS（前序遍历 + 深度参数）

如果你已经掌握了 BFS，也可以展示 DFS 的写法，体现你思维的开阔性：

function levelOrder(root) {
    const result = [];

    function dfs(node, depth) {
        if (!node) return;
        // 如果当前 depth 还没有对应的数组，则创建
        if (result.length === depth) {
            result.push([]);
        }
        result[depth].push(node.val);
        // 递归左、右子树，深度+1
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    }

    dfs(root, 0);
    return result;
}

面试官看到你写出两种写法，会认为你对树的遍历理解深刻。

---

五、 面试官必问的“连环追问” & 你的回应

追问 1： “如果不用 shift，怎么优化队列性能？”

你的回答：shift 在数组上是 O(n) 操作（因为要移动所有索引）。在数据量大的情况下，可以用双指针模拟队列：let head = 0，每次取 queue[head++]，最后用 queue.slice(head) 或直接忽略头部。这样入队是 push，出队是下标移动，全部 O(1)。

追问 2： “如果要求按‘之’字形打印（103 题），怎么改？”

你的回答：只需在 BFS 的基础上加一个布尔变量 leftToRight，每层切换。若为 false，则当前层结果 currentLevel.reverse() 再推入。

追问 3： “如果树的节点非常多（比如几百万），内存会爆，怎么处理？”

你的回答：在真实业务中，树通常不会这么深或宽。如果真的遇到，可以考虑流式处理（如使用生成器）或分页加载（只返回特定层级）。但在 LeetCode 场景下，O(n) 是必需的。

---

六、 面试时怎么说（话术模板）

“面试官，这道题我选择 BFS + 队列，因为层序遍历的本质是‘按层访问’。我通过 queue.length 固定每层的节点数，确保每层的数据独立成数组。时间复杂度 O(n)，空间复杂度 O(n)。如果您允许，我还可以给出递归 DFS 的实现，它的核心是传递深度参数，利用递归栈来模拟分层。”

最后强调一句：“这道题的 BFS 模板，可以轻松扩展到 N 叉树（429 题）、填充右侧指针（116 题） 等，我认为它是掌握树结构算法的‘基座’。”

树形结构的路径拼接（DFS 深度优先遍历）

下面给你两种解法：标准递归（最推荐，最清晰） 和 迭代栈（展示你懂如何避免递归爆栈），加上面试官可能会追问的“如果节点没有 children 字段怎么办”的兜底写法。

---

一、 解法一：DFS 递归（最符合直觉，面试首选）

核心思想：维护一个 currentPath 数组，每深入一层就把当前节点的 name 推进去，到达叶子节点（或遍历到当前节点时）就把路径记录到结果里。

function getTreePaths(root) {
    const result = [];

    // 递归函数：当前节点 + 从根节点到父节点的路径数组
    function dfs(node, pathArr) {
        if (!node) return;

        // 1. 将当前节点的名字加入路径数组
        pathArr.push(node.name);

        // 2. 将当前完整路径（用 '/' 连接）推入结果
        result.push(pathArr.join('/'));

        // 3. 递归处理子节点（如果有）
        if (node.children && node.children.length > 0) {
            for (const child of node.children) {
                dfs(child, pathArr);
            }
        }

        // 4. 【关键回溯】当前节点处理完毕，弹出自己的名字，以免影响兄弟节点
        pathArr.pop();
    }

    dfs(root, []);
    return result;
}

// 测试
const tree = {
  id: 1,
  name: '1',
  children: [
    {
      id: 2,
      name: '1-1',
      children: [
        { id: 4, name: '1-1-1', children: [] },
        { id: 5, name: '1-1-2', children: [] }
      ]
    },
    {
      id: 3,
      name: '1-2',
      children: [
        { id: 6, name: '1-2-1', children: [] }
      ]
    }
  ]
};
console.log(getTreePaths(tree));
// 输出：['1', '1/1-1', '1/1-1/1-1-1', '1/1-1/1-1-2', '1/1-2', '1/1-2/1-2-1']

为什么需要 pathArr.pop()？ 因为 pathArr 是引用类型，如果不弹出，遍历完左子树后，右子树会携带左子树的名字，导致路径错误。这是回溯算法最核心的一步！

---

二、 解法二：迭代栈（深层树推荐，避免递归调用栈溢出）

如果树很深（比如层级超过 1000），浏览器可能会报 Maximum call stack size exceeded。用显式栈可以规避这个问题。

function getTreePathsIterative(root) {
    if (!root) return [];

    const result = [];
    // 栈中存储：当前节点 和 从根节点到该节点的路径数组
    const stack = [{ node: root, path: [root.name] }];

    while (stack.length > 0) {
        const { node, path } = stack.pop();

        // 将当前路径加入结果
        result.push(path.join('/'));

        // 注意：为了保持输出顺序为 ['1', '1-1', '1-1-1', ...] (前序)
        // 由于栈是后进先出(LIFO)，为了保证子节点顺序从左到右，我们需要先把右边的子节点压入栈，再压左边的
        if (node.children && node.children.length > 0) {
            // 倒序遍历 children，这样正序的（左）会先被 pop 出来处理
            for (let i = node.children.length - 1; i >= 0; i--) {
                const child = node.children[i];
                stack.push({
                    node: child,
                    path: [...path, child.name] // 创建新数组，无需担心引用污染
                });
            }
        }
    }

    return result;
}

---

三、 面试官“连环追问” & 你的回应

追问 1：如果有的节点没有 children 字段，或者 children 是 null 怎么办？

你的回答：“我会增加健壮性判断，比如 const childNodes = node.children || [];，这样即使漏传了 children 属性，代码也不会报错。”

追问 2：如果树中出现了循环引用**（死循环），你的代码会崩溃吗？**

你的回答：“会。如果这是一个图而不是树，我需要用 Set 记录已访问的节点 id。在进入子节点前判断 if (visited.has(child.id)) return;，防止无限递归。”

追问 3：如果要求输出带有层级缩进的字符串，或者只输出叶子节点的路径，怎么改？

你的回答：

• 只输出叶子节点：在 dfs 中判断 if (!node.children || node.children.length === 0) 时才 result.push(path)。
• 带层级缩进：把 pathArr.join('/') 改成 pathArr.map((name, index) => ' '.repeat(index) + name).join('\n')。

---

四、 必背“面试话术”（讲给面试官听）

“面试官，我选择深度优先遍历（DFS），因为这道题天然符合‘先根后子’的递归结构。我维护一个路径数组，每当进入一个节点，我就记录当前完整路径，然后递归处理所有孩子。

特别注意：递归完当前节点的所有孩子后，一定要执行 pop() 操作，这是回溯的精髓，可以保证兄弟节点之间路径互不干扰。

复杂度：时间复杂度是 O(n)，因为每个节点只访问一次；空间复杂度在极端情况下（链状树）为 O(n)，对应递归调用栈的深度。”

把这段逻辑理清楚，并主动抛出“如果节点缺失 children”和“循环引用”的考量，面试官会认为你具备了生产级健壮性思维，而不是只会在 LeetCode 上刷题的选手。

// 有如下省市区信息
type CityData = {
  id: number;
  name: string;
  children?: CityData[];
};
const cityData: CityData[] = [
  {
    id: 1,
    name: '陕西省',
    children: [
      {
        id: 10,
        name: '西安市',
        children: [
          { id: 100, name: '新城区' },
          { id: 101, name: '长安区' },
          { id: 102, name: '雁塔区' },
        ],
      },
      {
        id: 11,
        name: '铜川市',
        children: [
          { id: 110, name: '王益区' },
          { id: 111, name: '印台区' },
          { id: 112, name: '耀州区' },
        ],
      },
    ],
  },
  {
    id: 2,
    name: '安徽省',
    children: [
      {
        id: 20,
        name: '合肥市',
        children: [
          { id: 200, name: '瑶海区' },
          { id: 201, name: '肥西县' },
          { id: 202, name: '肥东县' },
        ],
      },
      {
        id: 21,
        name: '芜湖市',
        children: [
          { id: 210, name: '镜湖区' },
          { id: 211, name: '鸠江区' },
          { id: 212, name: '南陵县' },
        ],
      },
    ],
  },
];

// 请实现一个方法，传入一个id值，如果在cityData中没有找到此id对应的信息则返回null，如果找到则返回此节点的枝干信息
// 比如：
// id为333，则返回null；
// id为10则返回[{ id: 1, name: '陕西省' }, { id: 10, name: '西安市' }]
// id为101则返回[{ id: 1, name: '陕西省' }, { id: 10, name: '西安市' }, { id: 101, name: '长安区' }] 再做下这道题

树形结构中的路径查找,核心是DFS（深度优先搜索）+ 回溯记录路径

下面我给出最优解（递归DFS），并附上面试官最常追问的“迭代防爆栈”写法，最后还会教你如何应对“如果树有环/数据量极大”的进阶场景。

---

一、 解法一：递归 DFS（最清晰，面试首选）

核心思路：

1. 从 cityData 的每个根节点（省）开始深度遍历。
2. 维护一个 path 数组，记录从根到当前节点的所有节点。
3. 若当前节点 id 匹配，则返回 path。
4. 否则递归遍历子节点，若在子树中找到，则返回结果。
5. 若所有节点遍历完都没找到，返回 null。

function findPathById(cityData, targetId) {
    // 深度优先搜索递归函数
    function dfs(node, path) {
        // 将当前节点加入路径（创建新数组，避免引用污染）
        const currentPath = [...path, node];

        // 如果找到目标，返回路径
        if (node.id === targetId) {
            return currentPath;
        }

        // 如果有子节点，递归查找
        if (node.children && node.children.length > 0) {
            for (const child of node.children) {
                const result = dfs(child, currentPath);
                if (result) return result; // 找到则提前返回
            }
        }

        // 当前分支没找到，返回 null
        return null;
    }

    // 遍历所有根节点（省份）
    for (const root of cityData) {
        const result = dfs(root, []);
        if (result) return result;
    }

    // 全都没找到
    return null;
}

测试验证：

console.log(findPathById(cityData, 333)); // null
console.log(findPathById(cityData, 10));  
// 输出：[{ id: 1, name: '陕西省' }, { id: 10, name: '西安市' }]
console.log(findPathById(cityData, 101)); 
// 输出：[{ id: 1, name: '陕西省' }, { id: 10, name: '西安市' }, { id: 101, name: '长安区' }]

---

二、 解法二：迭代栈（防止递归爆栈，面试加分项）

如果树的层级很深（比如 1000+），递归会导致 Maximum call stack size exceeded。此时可用显式栈替代。

function findPathByIdIterative(cityData, targetId) {
    // 栈中存储：当前节点 和 从根到该节点的路径数组
    const stack = [];

    // 初始化：将所有根节点压入栈
    for (const root of cityData) {
        stack.push({ node: root, path: [root] });
    }

    while (stack.length > 0) {
        const { node, path } = stack.pop();

        // 检查当前节点
        if (node.id === targetId) {
            return path;
        }

        // 如果有子节点，将子节点入栈（并传递新路径）
        if (node.children && node.children.length > 0) {
            for (const child of node.children) {
                stack.push({
                    node: child,
                    path: [...path, child] // 创建新路径
                });
            }
        }
    }

    return null;
}

注意：由于栈是 LIFO（后进先出），遍历顺序可能与递归不同，但不影响查找结果的正确性。

---

三、 复杂度分析

• 时间复杂度：最坏情况遍历所有节点，O(n)，n 为节点总数。
• 空间复杂度：
  • 递归版：递归调用栈深度为树的高度，最坏 O(h)，h 为树高；加上 path 数组 O(h)，总体 O(h)。
  • 迭代版：栈大小 O(n)（最坏情况所有节点在栈中），path 数组 O(h)，总体 O(n)。

---

四、 面试官“连环追问” & 你的回应

追问 1：如果数据量非常大（几百万个节点），你的递归方法可能会爆栈，怎么优化？

回答：“我会改用迭代栈（如上所示），完全消除递归深度限制。还可以考虑用 BFS（广度优先） 逐层查找，但 BFS 需要额外存储每一层的路径，内存占用可能会更大。对于这种‘单点查找’需求，迭代 DFS 是最平衡的选择。”

追问 2：如果树中出现了循环引用**（子节点指向祖先），你的代码会死循环吗？怎么防御？**

回答：“会。我可以在递归/迭代中增加一个 visited 集合（如 Set 存储节点 id），在进入节点前检查是否已访问过。若已访问则跳过，避免死循环。但在这个省市区数据中，不存在环，所以可以不实现。若要做到健壮，我会加上此检查。”

追问 3：如果我想同时知道目标节点的父级信息**，你会怎么改？**

回答：“现在的 path 已经包含了从根到目标的所有节点，所以父级就是 path[path.length - 2]（如果存在）。如果只想要节点的 id 数组，可以 path.map(node => node.id)。”

追问 4：如果 cityData 不是数组，而是一个节点对象（单根树），怎么改？

回答：“那就直接 dfs(root, [])，无需遍历数组。或者我可以封装一个通用函数，兼容数组或对象。”

---

五、 必背“面试话术”（讲给面试官听）

“面试官，这道题我选择了深度优先遍历（DFS）+ 回溯路径。因为我们需要找到从根到目标节点的完整链路，DFS 天然适合这种‘路径累积’的场景。

关键点：在递归过程中，我每次都创建新的路径数组 [...path, node]，而不是直接修改 path，这样可以避免分支之间相互污染，也无需手动 pop 回溯。

复杂度：每个节点只访问一次，时间复杂度 O(n)；空间上，最坏情况递归深度为树高，空间 O(h)。

额外优化：如果树的层级非常深，我会改用迭代栈来规避递归爆栈风险。另外，若数据可能存在循环引用，我会用 visited 集合进行防环处理。”