Lstmxx的空间

1104. 二叉树寻路

在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。

如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；

而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。

链接

function pathInZigZagTree(label: number): number[] {
  let depth = 0
  let total = 0
  let res: number[] = []
  const depMap: Record<number, number> = {}
  while(total < label) {
    depth++
    depMap[depth] = 2 ** (depth - 1)
    total += depMap[depth]
  }
  while(depth > 0) {
    const start = 2 ** (depth - 1)
    const len = depMap[depth]
    res.unshift(label)
    label = Math.floor(((start + len - 1 - label) + start) / 2)
    depth--
  }
  return res
};