1104. 二叉树寻路

发表于 | 分类于
没解出啊

1104. 二叉树寻路

第一时间想的是构造二叉树，然后利用每层对称的关系 ，求出父节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var pathInZigZagTree = function(label) {
    let stack = []
    for(let i = 1 ; i <=  label ; i ++) {
      let level = Math.floor(Math.log(i) / Math.log(2)) 
      if (!stack[level]) { stack[level] = [] }
      if (level % 2 === 0)  {
        stack[level].push(i)
      } else {
        stack[level].unshift(i)
      }
    }
    var level = Math.floor(Math.log(label) / Math.log(2)) 
    let ans = []
    while (level) {
      ans.push(label)
      level--
      label = Math.floor(label / 2)
      let index = stack[level ].length - 1 -  stack[level ].indexOf(label)
      label = stack[level][index]
    }
    ans.push(1)

    return ans.reverse()
};

很遗憾，超时了。

受到答案的启发，既然是对称的，同层数时，对称的数之和相同。

一层的首项为 2^ n ，末项是 2^(n + 1) - 1 可的对称数 2^ n + 2^(n + 1) - 1 - x

即

( 1 << row ) + ( 1 << (row + 1) ) - 1 - label;

查找的末位一定是1，可做while 的结束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var pathInZigZagTree = function(label) {
  let row = Math.floor( Math.log(label) / Math.log(2) )
  let ans = []
  while(label!==1) {
    ans.unshift(label)
    row --
    label = getReverse(Math.floor(label / 2),row)
  }
  ans.unshift(1)
  return ans
};

const getReverse = (label, row) => {
  return (1 << row ) + (1 << (row + 1)  ) - 1  - label;
}