leetcode 1104 二叉树寻路

leetcode 1104 二叉树寻路

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

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

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

给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。

示例 1：

输入：label = 14
输出：[1,3,4,14]
示例 2：

输入：label = 26
输出：[1,2,6,10,26]

提示：

1 <= label <= 10^6

分析

• 根据label可以求出从root节点到label的高度
• 设label所在的层为 m (1,2…,m),则第m层的起始节点值 $start_m = 2^{m-1}$startm​=2m−1,第m 层有$2^{m-1}$2m−1 个数字：

  $2^{m-1},2^{m-1}+1,2^{m-1}+2,...,2^m-1$2m−1,2m−1+1,2m−1+2,...,2m−1

• 如果m层为奇数层，则m层的数字排序如上
• 如果m层位偶数层，则m层的数字排序需要翻转

  $2^{m}-1,2^{m}-2,2^{m}-3,...,2^{m-1}$2m−1,2m−2,2m−3,...,2m−1

• 已知label的值，根据以上分析，可以求得label在m层中相对与左边的位置索引 index
• $index/2$index/2 就是其父节点在m-1层的相对左侧的索引，依据上述方法可以求得其父节点的label，递归进行，可以获得从label到root的一条路径，翻转后既是所求

code

class Solution {
public:
    vector<int> pathInZigZagTree(int label) {
    	// lable所在的层数(0,1,...)
        int height =31;
        int bit = 0x01<<31;
        while(height>=0 && !(label&bit)){
            bit>>=1;
            height--;
        }
        vector<int> res;
        while(height>=0){
            res.push_back(label);
            //label为1时，已经是root节点，直接退出
            if(label == 1) break;
            int nums = pow(2,height);
            int start = nums;
            int index = label - start;
            if(height%2 == 1) {
                index = nums -1 - index;
            }
            //父节点相对于层左边的索引
            int parent_index = index / 2;
            height--;
            nums = pow(2,height);
            start = nums;
            //父节点值
            if(height % 2 == 1 ){
                label = start + nums - 1 - parent_index;
            }else{
                label = start + parent_index;
            }
        }
        //翻转
        int i =0,j = res.size()-1;
        while(i < j){
            swap(res[i],res[j]);
            i++;j--;
        }
        return res;

    }
};