【力扣】1104. 二叉树寻路

vlambda
2021-08-09

【力扣】1104. 二叉树寻路

1104. 二叉树寻路

七月

难度：中等

https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/

题目

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

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

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

【力扣】1104. 二叉树寻路

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

示例

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

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

 
   
   
 
  
    
    
   
    
     
     
 
     
     
      
      
 
      
      
      提示
 
      
      
      
 
      
     
     
     
 
     
    
  
 
   
   
 


 
   
   
 
  
    
    
  1 <= label <= 10^6
 
   
   
 
 
   
   
 
  
    
    
   
    
     
     
 
     
     
      
      
 
      
      
      题目分析
 
      
      
      
 
      
     
     
     
 
     
    
  
 
   
   
 


 
   
   
 
  
    
    
  依照题目不难发现父节点和子节点之间的联系和规律。

  
    
    
  思路是第 y 层的第 x 个为 label 的结点，
其父结点必然是位于第 y-1 层的
第 pow(2,y-1)-(x-1)/2 个 为 label-(x+(x-1)/2)的结点
 
   
   
 


 
   
   
 
  
    
    
   
    
     
     
 
     
     
      
      
 
      
      
      解题
 
      
      
      
 
      
     
     
     
 
     
    
  
 
   
   
 
 
   
   
 
  
    
    
   
    
     
      
       
       
 
       
      
     
    
  
 
   
   
 
‍‍‍‍
 
   
   
 
  
    
    
   
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
  
  
    
    
  class Solution {public: vector<int> pathInZigZagTree(int label) { int y = 1;//第几层 int x = label;//所在层从小到大 第几个 while( x > pow(2,y-1)){ x -= pow(2,y-1); y++; } vector<int> res; res.push_back(label);        while(y>1){ y--; label -=x+(x-1)/2;//计算父结点 x = pow(2,y-1)-(x-1)/2;//计算父结点的位置 res.push_back(label);  } reverse(res.begin(),res.end()); return res; }};
 
   
   
 


 
   
   
 
  
    
    
   
    
     
      
       
        
        你每日一题了吗？ 
        
       
      
      
       
        
        欢迎指正喔～～