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

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

## Topic ##

*  Math
 *  Binary Tree

## Description ##

[https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree/][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.

![a041964f6316c6e013fe6e908462ebf7.png][]

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));
            
        }
    }

[https_leetcode.com_problems_path-in-zigzag-labelled-binary-tree]: https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree/
[a041964f6316c6e013fe6e908462ebf7.png]: /images/20221005/43a7dc4b3565463f9b24795ffad2a405.png