← 返回完整题库
Typescript简单

请实现下面的 treePath 方法

参考答案

题目意图

给定树形结构,返回从根节点到目标节点的路径。

实现(DFS + 回溯)

interface TreeNode {
  id: number;
  children?: TreeNode[];
}

function treePath(tree: TreeNode[], targetId: number): number[] | null {
  const path: number[] = [];

  const dfs = (nodes: TreeNode[]): boolean => {
    for (const node of nodes) {
      path.push(node.id);
      if (node.id === targetId) return true;
      if (node.children && dfs(node.children)) return true;
      path.pop();
    }
    return false;
  };

  return dfs(tree) ? path : null;
}

关键点

  1. 进入 push、失败 pop:保证 path 始终是当前遍历链,天然就是根到当前节点的路径。
  2. 找到即 return true:一路冒泡,其他分支不再遍历。
  3. 输入是森林(数组),若题目给的是单根节点,把参数改成 TreeNode 并在外层包一层 [root]。
  4. 找不到返回 null,与"根节点即目标"(返回 [rootId])区分开。
  5. 树很深时递归可能栈溢出,可改迭代 + parent Map 回溯构造路径。
  6. 若要返回节点对象数组,把 path 类型改为 TreeNode[] 并 push 节点本身(注意回溯 pop 同步)。

复杂度

时间 O(n)(最坏遍历全部节点),空间 O(h)(递归深度/路径长度)。

本题来自 计算机知识面试题库,共 921 道题。