一定要早日上岸鸭 · July 29, 2021 0

1104. 二叉树寻路

1104. 二叉树寻路

思路:

本题有两种解法,第一种是模拟第二种是用数学的方法,首先要考虑的是若一个二叉树没有奇偶性质,那么他的父节点一定是 当前节点/2;因此,在得知某一层的最大值和最小值后,我们便可以由计算或模拟来得到其父节点:

利用从根节点到任意一层都是满二叉树,我们可以先确定 label 所在的层级 level,然后计算出当前层起始节点值(最小值)和结束节点值(最大值)。再利用「每层节点数量翻倍」&「隔层奇偶性翻转」,寻址出上一层的节点下标(令每层下标均「从左往右」计算,并从 11 开始),直到构造出答案(寻址到根节点)。

如果二叉树本身不具有奇偶性翻转的话,显然某个节点 xx 的父节点为 ⌊x/2⌋,但事实上存在奇偶性翻转,而在解法一中我们已经可以 O(1) 计算某一层的起始值和结束值,有了「起始值 & 结算值」和「当前节点所在层的相对位置」,只需要利用“对称性”找到父节点在上层的相应位置,然后根据相应位置算出父节点值即可。

代码:

class Solution { public int getStartforeachRow(int level){ return (int)Math.pow(2, level-1); } public int getEndforeachRow(int level){ return 2*getStartforeachRow(level)-1; } // 模拟的方法: // public List<Integer> pathInZigZagTree(int label) { // // int level = (int) Math.log(label)/Math.log(2)+1; // int level = 1; // while(getEndforeachRow(level)<label) level++; // int[] ret = new int[level]; // int idx = level-1, cur = label; // while(idx>=0){ // ret[idx--] = cur; // if(level%2==0){ // // 偶数层: // int j = (int)Math.pow(2, level-1)/2; // for(int i=getStartforeachRow(level); i<getEndforeachRow(level); i+=2, j--){ // if(i==cur || i+1==cur) break; // } // int prev = getStartforeachRow(level-1); // while(j-->1) prev++; // cur = prev; // } // else{ // int j = 1; // for(int i=getStartforeachRow(level); i<getEndforeachRow(level); i+=2, j++){ // if(i==cur || i+1==cur) break; // } // int prev = getEndforeachRow(level-1); // while(j-->1) prev--; // cur = prev; // } // level--; // } // List<Integer> res = new ArrayList<Integer>(); // for(int i:ret) res.add(i); // return res; // } // 数学: public List<Integer> pathInZigZagTree(int label) { int level = 1; while(getEndforeachRow(level)<label) level++; int idx = level-1, cur = label; int[] ans = new int[level]; while(idx>=0){ ans[idx--] = cur; int prev = ((1<<level)-1-cur)>>1; // System.out.println(prev); cur = getStartforeachRow(level-1)+prev; level--; } List<Integer> ret = new ArrayList<>(); for(int i:ans) ret.add(i); return ret; } }