请实现下面的 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;
}
关键点
- 进入 push、失败 pop:保证
path始终是当前遍历链,天然就是根到当前节点的路径。 - 找到即 return true:一路冒泡,其他分支不再遍历。
- 输入是森林(数组),若题目给的是单根节点,把参数改成
TreeNode并在外层包一层[root]。 - 找不到返回
null,与"根节点即目标"(返回[rootId])区分开。 - 树很深时递归可能栈溢出,可改迭代 + parent Map 回溯构造路径。
- 若要返回节点对象数组,把
path类型改为TreeNode[]并 push 节点本身(注意回溯 pop 同步)。
复杂度
时间 O(n)(最坏遍历全部节点),空间 O(h)(递归深度/路径长度)。