1104. 二叉树寻路

ゞ浴缸里的玫瑰 2022-12-22 15:29 106阅读 0赞

# 题目来源 #

[1104. 二叉树寻路][1104.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

# 题目解析 #

## 公式 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]  
如果是按照正常顺序构造二叉树，理应是

1
            2                    3
       4         5          6          7 
    8     9   10    11   12    13   14    15 
    ....

因为题目给出的是个完全二叉树，下一层的节点是当前层的2倍。

假设 l a b e l = 14 label = 14 label=14，顺序构造的上一层  l a b e l / 2 = 7 label / 2 = 7 label/2=7  
但是按照原图来看理应是 4 4 4才符合结果 。  
假设  l a b e l = 11 label = 11 label=11，顺序构造的上一层  l a b e l / 2 = 5 label / 2 = 5 label/2=5  
但是按照原图来看理应是 6 6 6才符合结果。  
此时可以看到按照之行排列的计算结果是顺序排列的 对称点`(7 >< 4)、(6 >< 5)`

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 2]

class Solution {
        
    public static List<Integer> pathInZigZagTree(int label) {
        
            List<Integer> list = new LinkedList<>();
    
            int level = (int)(Math.log(label) / Math.log(2)); // label的上一层
    
            while ( label > 0){
        
                list.add(label);
                label = 3 * (int)(Math.pow(2, --level)) - 1 -  label / 2;
            }
    
            Collections.reverse(list);
            return list;
        }
    }

![在这里插入图片描述][20201120194022940.png_pic_center]

[1104.]: https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/978162d0cf054d4ea1adba2c73b3d205.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/f1d7e261e0a14a75bef4d4f5c036db74.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/23cdca9b9c7b4a42ace0091471337413.png
[20201120194022940.png_pic_center]: /images/20221120/712586b51c264eadbe4f888f61b3c733.png