1104-二叉树寻路

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

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 的结束

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;}

Siqi Liu / 1104-二叉树寻路