LeetCode - Medium - 1104. Path In Zigzag Labelled Binary Tree-蒲公英云

LeetCode - Medium - 1104. Path In Zigzag Labelled Binary Tree

港控/mmm° 2022-10-11 15:00 252阅读 0赞

Topic

Math
Binary Tree

Description

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

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 < = l a b e l < = 1 0 6 1 <= label <= 10^6 1<=label<=106

Analysis

The tree in problem reminds me of binary number representation.

Let’s use label 26 for example.
26 = 0b11010

If the tree is a normal full complete binary tree, the label 26 ‘s parent label should be :
26 >> 1 = 0b1101 = 13

But the correct label is 10 because of Zigzag.
10 = 0b1010

If you try 10 + 13：
10 + 13 = 23 = 0b10111

And the label 26 ‘s level minimum label is 16, maximum label is 31。
16 = 0b10000
31 = 0b11111

And (16 + 31) >> 1 = 23 = 10 + 13。 What a happy accident!
(16 + 31) >> 1 = 0b101111 >> 1 = 0b10111 = 23

So, we can use this formula to get the label 26 ‘s parent label:
(minimum + maximum) >> 1 - current >>1 = (16 + 31) >> 1 - 26 >> 1 = 10

Enjoy code!

Submission

import java.util.LinkedList;
import java.util.List;
public class PathInZigzagLabelledBinaryTree { 
    public List<Integer> pathInZigZagTree(int label) { 
        List<Integer> result = new LinkedList<>();
        while(label > 0) { 
            result.add(0, label);
            if(label == 1) break;
            int min = 1;
            for(int i = 1; (label >>> i) > 0; i++)
                min <<= 1;
            label = ((min + (min << 1) - 1) >> 1) - (label >> 1);
        }
        return result;
    }
}

Test

import static org.junit.Assert.*;
import org.hamcrest.collection.IsIterableContainingInOrder;
import org.junit.Test;
public class PathInZigzagLabelledBinaryTreeTest { 
    @Test
    public void test() { 
        PathInZigzagLabelledBinaryTree pObj = new PathInZigzagLabelledBinaryTree();
        assertThat(pObj.pathInZigZagTree(26), IsIterableContainingInOrder.contains(1,2,6,10,26));
        assertThat(pObj.pathInZigZagTree(14), IsIterableContainingInOrder.contains(1,3,4,14));
    }
}