1104.二叉树寻路

链接：1104.二叉树寻路
难度：Medium
标签：树、数学、二叉树
简介：给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。

题解 1 - typescript

• 编辑时间：2021-07-29
• 执行用时：88ms
• 内存消耗：39.6MB
• 编程语言：typescript
• 解法介绍：深度向上遍历。

function pathInZigZagTree(label: number): number[] {
  const list: number[] = [];
  let max = 1;
  while (label >= max) list.push((max <<= 1));
  const ans: number[] = [];
  dfs(label);
  return ans;
  function find(label: number): {
    maxLabel: number;
    prevMin: number;
  } {
    for (let i = 0; i < list.length; i++) {
      if (list[i] > label)
        return {
          maxLabel: list[i] - 1,
          prevMin: list[i - 2] ?? 1,
        };
    }
    return {
      maxLabel: -1,
      prevMin: -1,
    };
  }
  function dfs(label: number): void {
    if (label === 1) {
      ans.unshift(label);
      return;
    }
    ans.unshift(label);
    const { maxLabel, prevMin } = find(label);
    let i = maxLabel;
    let parent = prevMin;
    while (i > label) {
      i--;
      if ((i & 1) !== 0) parent++;
    }
    dfs(parent);
  }
}