leetcode 1104 二叉树寻路

标签: leetcode解题

leetcode 1104 二叉树寻路

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

如下图所示,在奇数行(即,第一行、第三行、第五行……)中,按从左到右的顺序进行标记;
picture

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

给你树上某一个节点的标号 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层的起始节点值 startm=2m1start_m = 2^{m-1},第m 层有2m12^{m-1} 个数字:

    2m1,2m1+1,2m1+2,...,2m12^{m-1},2^{m-1}+1,2^{m-1}+2,...,2^m-1

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

    2m1,2m2,2m3,...,2m12^{m}-1,2^{m}-2,2^{m}-3,...,2^{m-1}

  • 已知label的值,根据以上分析,可以求得label在m层中相对与左边的位置索引 index
  • index/2index/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;

    }
};
版权声明:本文为weixin_41964962原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_41964962/article/details/104842313