1104. 二叉树寻路

偏执的太偏执、 2023-10-04 18:52 8阅读 0赞

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

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

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

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

示例 1：

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

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

提示：

1 <= label <= 10^6

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/path-in-zigzag-labelled-binary-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：数学  
我们先来研究一个简单的情形：二叉树的每一行都是按从左到右的顺序进行标记。此时二叉树满足以下性质：

根节点位于第 11 行；

第 ii 行有 2^\{i-1\}2  
i−1  
个节点，最左边的节点标号为 2^\{i-1\}2  
i−1  
，最右边的节点标号为 2^i-12  
i  
−1；

对于标号为 \\textit\{val\}val 的节点，其左子节点的标号为 2 \\times \\textit\{val\}2×val，右子节点的标号为 2 \\times \\textit\{val\} + 12×val+1，当 \\textit\{val\}>1val>1 时，其父节点的标号为 \\lfloor \\frac\{\\textit\{val\}\}\{2\} \\rfloor⌊  
2  
val  
  
⌋。

对于给定节点的标号 \\textit\{label\}label，可以根据上述性质得到从该节点到根节点的路径，将路径反转后，即为从根节点到标号 \\textit\{label\}label 的节点的路径。

回到这题，对于偶数行按从右到左的顺序进行标记的情况，可以转换成按从左到右的顺序进行标记的情况，然后按照上述思路得到路径，只要对偶数行的标号进行转换即可。为了表述简洁，下文将按从左到右的顺序进行标记时的节点的标号称为「从左到右标号」。

首先找到标号为 \\textit\{label\}label 的节点所在的行和该节点的「从左到右标号」。为了找到节点所在行，需要找到 ii 满足 2^\{i-1\} \\le \\textit\{label\} < 2^i2  
i−1  
≤label<2  
i  
，则该节点在第 ii 行。该节点的「从左到右标号」需要根据 ii 的奇偶性计算：

当 ii 是奇数时，第 ii 行为按从左到右的顺序进行标记，因此该节点的「从左到右标号」即为 \\textit\{label\}label；

当 ii 是偶数时，第 ii 行为按从右到左的顺序进行标记，将整行的标号左右翻转之后得到按从左到右的顺序进行标记的标号，对于同一个节点，其翻转前后的标号之和为 2^\{i-1\} + 2^i - 12  
i−1  
\+2  
i  
−1，因此标号为 \\textit\{label\}label 的节点的「从左到右标号」为 2^\{i-1\} + 2^i - 1 - \\textit\{label\}2  
i−1  
\+2  
i  
−1−label。

得到标号为 \\textit\{label\}label 的节点的「从左到右标号」之后，即可得到从该节点到根节点的路径，以及路径上的每个节点的「从左到右标号」。对于路径上的每个节点，需要根据节点所在行的奇偶性，得到该节点的实际标号：

当 ii 是奇数时，第 ii 行的每个节点的「从左到右标号」即为该节点的实际标号；

当 ii 是偶数时，如果第 ii 行的一个节点的「从左到右标号」为 \\textit\{val\}val，则该节点的实际标号为 2^\{i-1\} + 2^i - 1 - \\textit\{val\}2  
i−1  
\+2  
i  
−1−val。

最后，将路径反转，即可得到从根节点到标号 \\textit\{label\}label 的节点的路径。

作者：LeetCode-Solution  
链接：https://leetcode.cn/problems/path-in-zigzag-labelled-binary-tree/solution/er-cha-shu-xun-lu-by-leetcode-solution-ryx0/  
来源：力扣（LeetCode）  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
        public List<Integer> pathInZigZagTree(int label) {
            int row = 1, rowStart = 1;
            while (rowStart * 2 <= label) {
                row++;
                rowStart *= 2;
            }
            if (row % 2 == 0) {
                label = getReverse(label, row);
            }
            List<Integer> path = new ArrayList<Integer>();
            while (row > 0) {
                if (row % 2 == 0) {
                    path.add(getReverse(label, row));
                } else {
                    path.add(label);
                }
                row--;
                label >>= 1;
            }
            Collections.reverse(path);
            return path;
        }
    
        public int getReverse(int label, int row) {
            return (1 << row - 1) + (1 << row) - 1 - label;
        }
    }
    
    作者：LeetCode-Solution
    链接：https://leetcode.cn/problems/path-in-zigzag-labelled-binary-tree/solution/er-cha-shu-xun-lu-by-leetcode-solution-ryx0/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思路：

我们先不考虑题目中特殊化的二叉树，先思考如何恢复正常的二叉树的路径

补充知识：  
若已知一节点为 ii，则该节点的左孩子节点为 (2 \* i)(2∗i)，右孩子节点为 (2 \* i + 1)(2∗i+1)  
且该节点的父节点为 (i \\,/\\, 2)(i/2)

对于正常的二叉树，已知节点 ii，根据上述知识我们便可以求得其路径：

作者：L-Sheng  
链接：https://leetcode.cn/problems/path-in-zigzag-labelled-binary-tree/solution/1104-er-cha-shu-xun-lu-c-100-jie-fa-wei-p3ik1/  
来源：力扣（LeetCode）  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

观察题目要求的二叉树，其实不难发现：deepdeep 为偶数时和正常的二叉树是对称的，所以我们只需要对 deepdeep 为偶数时进行处理即可

那么我们如何将正常的数转化为我们需要的呢？

补充知识：  
二叉树中第 ii 层一共有 2 ^ \{(i-1)\}2  
(i−1)  
个数，且前 i - 1i−1 层共有 2 ^ \{(i-1)\} - 12  
(i−1)  
−1 个数  
注意： 这里的 ii 从 11 开始，而在代码实现中 ii 从 00 开始

为了和代码一致，下面的推导我们以 i = 0i=0 为第一层

以节点 1010 举例，假设节点 1010 的深度为 ii，节点 1010 对应的是节点 1313，首先我们需要第 ii 层的节点个数以及第 ii 层的第一个节点的编号 ll 和最后一个节点的编号 rr

其实不难发现：

l = 2^i\\\\ r = 2 \* l - 1\\\\ 13 = r - 10 + l  
l=2  
i  
  
r=2∗l−1  
13=r−10+l

由此我们可以根据节点 1010 求得节点 1313

最后需要注意的是：要对 ansans 进行反转

代码实现：

class Solution \{  
public:  
vector<int> pathInZigZagTree(int label) \{  
vector <int> ans;  
while(label) \{  
ans.push\_back(label);  
label >>= 1;  
\}  
reverse(ans.begin(), ans.end());  
int l, r, deep = ans.size();  
for(int i = 0; i < deep; i++) \{  
if((deep & 1) != (i & 1)) continue; // 判断第 i 层是否需要修改  
l = (1 << i);  
r = l + l - 1;  
ans\[i\] = r - ans\[i\] + l;  
\}  
return ans;  
\}  
\};  
具体解释一下代码中的 (deep\\; \\&\\; 1)(deep&1) !=!= (i\\; \\&\\; 1)(i&1)

当 deepdeep 为 偶数 时，只对 奇数深度 进行修改  
当 deepdeep 为 奇数 时，只对 偶数深度 进行修改  
而 deepdeep 为二叉树的总深度，ii 为当前遍历的深度，我们可以通过 deep\\; \\&\\; 1deep&1 可以判断 deepdeep 的奇偶  
如果 (deep\\; \\&\\; 1)(deep&1) !=!= (i\\; \\&\\; 1)(i&1) 说明 deepdeep 和 ii 具有不同的奇偶性，此时需要对第 ii 层进行修改，但由于 i = 0i=0 为第一层，所以此时需要将 ii 理解为 i + 1i+1 才是当前真实的深度，故当 (deep\\; \\&\\; 1)(deep&1) !=!= (i\\; \\&\\; 1)(i&1) 时不需要修改

复杂度分析

时间复杂度：O(\\log label)O(loglabel)，求二叉树层数需 O(\\log label)O(loglabel)，ans.size() = \\log labelans.size()=loglabel，则反转一次 ansans 需 O(\\log label)O(loglabel)，遍历一次 ansans 需 O(\\log label)O(loglabel)，总体为 O(\\log label)O(loglabel)

空间复杂度：O(1)O(1)，除返回需要的 ansans 外，额外需要的空间为 O(1)O(1)

class Solution {
        public List<Integer> pathInZigZagTree(int label) {
           List<Integer> ans = new ArrayList<>();
           while(label>0){
               ans.add(label);
               label>>=1;
           }
           Collections.reverse(ans);
           int l, r, deep = ans.size();
            for(int i = 0; i < deep; i++) {
                if((deep & 1) != (i & 1)) continue;     // 判断第 i 层是否需要修改
                l = (1 << i);
                r = l + l - 1;
                ans.set(i,r - ans.get(i) + l);
            }
            return ans;
    
        }
    
    }