电子商务网站建设系统特点,楚雄市网站建设公司,精品下载站,有域名一定要买空间做网站在一棵无限的二叉树上#xff0c;每个节点都有两个子节点#xff0c;树中的节点 逐行 依次按 “之” 字形进行标记。
如下图所示#xff0c;在奇数行#xff08;即#xff0c;第一行、第三行、第五行……#xff09;中#xff0c;按从左到右的顺序进行标记#xff1b;…在一棵无限的二叉树上每个节点都有两个子节点树中的节点 逐行 依次按 “之” 字形进行标记。
如下图所示在奇数行即第一行、第三行、第五行……中按从左到右的顺序进行标记
而偶数行即第二行、第四行、第六行……中按从右到左的顺序进行标记。
给你树上某一个节点的标号 label请你返回从根节点到该标号为 label 节点的路径该路径是由途经的节点标号所组成的。
示例 1
输入label 14 输出[1,3,4,14] 示例 2
输入label 26 输出[1,2,6,10,26]
解题思路
利用二叉树的性质编号为n的子节点父节点为n/2因为n为int所以才可以这样算因此我们这题就是需要不断往上找父节点因为树中的节点 逐行 依次按 “之” 字形进行标记正常二叉树编号每一层从左到右的顺序进行标记而偶数层在这题是相反的但是我们可以把顺序的节点映射为反序来加入结果列表因此我们这次只需要按正常完全二叉树的编号去寻找父节点当遇到父节点在偶数层的时候将节点映射为反序的加入结果列表。
代码
class Solution {public ListInteger pathInZigZagTree(int label) {int i0;while (Math.pow(2,i)label){i;}ListInteger listnew ArrayList();i--;if (i%21){label3* (int) Math.pow(2,i)-1-label;}while (i0){list.add(i%21?3* (int) Math.pow(2,i)-1-label:label);label/2;i--;}Collections.reverse(list);return list;}
}
