[LeetCode] 1104. Path In Zigzag Labelled Binary Tree

[frdmu]

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,...), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,...), the labelling is right to left.

Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.

 

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output: [1,2,6,10,26]

 

Constraints:

• 1 <= label <= 10^6
   
   

解法：
这道题看着挺唬人，其实就是找规律。很显然，如果不论什么正序反序，根据完全二叉树的规则，可以根据子节点算出父节点。
比如示例一，根据14，可以算出到达他的路径是[1, 3, 7, 14]，无非就是一直除2。与答案不用就在于加了个正序反序，怎么根据7
算4，很简单，可以看出在第三层，每一个对应位置的结点，都有规律，4对应7，5对应6，他们的和是一定，所以只要算出这个和，再减7，就是4了。
代码如下：

class Solution {
public:
    int bound(int row) {
        int sum = 1;
        int n = 1;
        
        while (n <= row) {
            sum *= 2;  
            n++;
        }
        
        return sum-1;
    }
    vector<int> pathInZigZagTree(int label) {
        vector<int> res = {{1}};
        
        while (label != 1) {
            res.push_back(label);
            label /= 2;
        }
        sort(res.begin(), res.end());
        int n = res.size();
        if (n % 2 == 0) {
            for (int i = 2; i < n; i++) {
                if (i%2 != 0) {
                    res[i-1] = bound(i-1) + bound(i) + 1 - res[i-1];     
                }
            }    
        } else {
            for (int i = 2; i < n; i++) {
                if (i%2 == 0) {
                    res[i-1] = bound(i-1) + bound(i) + 1 - res[i-1];     
                }
            }    
        }
        
        return res;
    } 
};