Leetcode 1104: Path In Zigzag Labelled Binary Tree
You are given a label representing a node in an infinite binary tree. In this binary tree, each level alternates between left-to-right and right-to-left labeling. Your task is to return the path from the root of the tree to the node with the given label, following the zigzag pattern.
Problem
Approach
Steps
Complexity
Input: You are given an integer `label`, which represents the label of a node in the zigzag binary tree.
Example: label = 10
Constraints:
• 1 <= label <= 10^6
Output: You should return an array of integers, representing the labels from the root of the tree to the node with the given label, in the correct order.
Example: [1, 3, 6, 10]
Constraints:
• The returned array should be in ascending order from the root to the node.
Goal: To find the path from the root to the node with the given label in the zigzag binary tree.
Steps:
• Determine the level of the given node by calculating the logarithm of the label.
• Starting from the given node, trace the path back to the root by repeatedly computing the parent of the current node.
• At each level, adjust the calculation based on whether the level is odd or even, to account for the zigzag pattern.
Goal: The tree is an infinite binary tree, and you need to find the path from the root to a node with a given label.
Steps:
• The binary tree has infinite depth.
• The tree's nodes are labeled in zigzag fashion, alternating left-to-right and right-to-left on each level.
Assumptions:
• The given label is valid and corresponds to a node in the tree.
• The level of the given node can be determined using logarithmic operations.
• Input: Input: label = 10
• Explanation: The node with label 10 lies at level 4, and the path from the root to this node is [1, 3, 6, 10]. At level 4, the node is labeled from right to left, so the pattern is followed accordingly.
Approach: The goal is to find the path from the root to the given node by working backwards from the label, adjusting the calculation for each level based on whether it is odd or even.
Observations:
• The binary tree alternates labeling direction at each level.
• Finding the level of the node helps determine its position in the tree.
• Start from the given label and move upwards to the root, adjusting the label at each level based on the zigzag pattern.
Steps:
• Calculate the level of the node using logarithmic functions.
• Start at the node and trace the path upwards, adjusting the label for each parent node depending on whether the current level is odd or even.
• Store each node label in the path, and reverse the list to return the path from root to the given label.
Empty Inputs:
• The input is guaranteed to always be a valid label within the given range.
Large Inputs:
• The label can be as large as 10^6, so the solution should efficiently handle large inputs.
Special Values:
• The root node is always labeled 1, and the solution should correctly handle this case.
Constraints:
• The tree has infinite depth, so the solution must work efficiently for all labels within the range.
class Solution {
public:
vector<int> pathInZigZagTree(int label) {
vector<int> res;
res.push_back(label);
int level = log2(label);
while (level != 0) {
int left = pow(2 , (level - 1));
int right = pow(2 , level) - 1;
label = left + ( right- label / 2);
res.push_back(label);
level -= 1;
}
int num = res.size();
reverse(res.begin(), res.end());
return res;
}
1 : Class Declaration
class Solution {
The class declaration for the `Solution` class, which contains the method to solve the problem.
2 : Access Modifier
public:
The access modifier `public` indicates that the members of the class can be accessed from outside the class.
3 : Method Declaration
vector<int> pathInZigZagTree(int label) {
This method `pathInZigZagTree` takes an integer `label` as input and returns a vector of integers representing the path in the zigzag binary tree.
4 : Variable Declaration
vector<int> res;
A vector `res` is declared to store the path from the label to the root of the tree.
5 : Push to Vector
res.push_back(label);
The label is added to the `res` vector as the first node in the path.
6 : Level Calculation
int level = log2(label);
The level of the tree at which the label is located is calculated using the logarithm base 2 of the label.
7 : Loop Start
while (level != 0) {
A while loop is used to trace the path from the label to the root of the tree. It continues until the root is reached.
8 : Left Node Calculation
int left = pow(2 , (level - 1));
The leftmost node at the current level is calculated as (2^{ ext{level}-1}).
9 : Right Node Calculation
int right = pow(2 , level) - 1;
The rightmost node at the current level is calculated as (2^{ ext{level}} - 1).
10 : Label Update
label = left + ( right- label / 2);
The label is updated based on the current level's nodes. The formula adjusts the label for the zigzag pattern.
11 : Push to Vector
res.push_back(label);
The updated label is added to the `res` vector.
12 : Level Decrement
level -= 1;
The level is decremented by 1, moving upwards in the tree.
13 : Reverse Vector
reverse(res.begin(), res.end());
The vector `res` is reversed because the path was collected from the label to the root and needs to be reversed to show the path from the root to the label.
14 : Return Statement
return res;
The method returns the vector `res` containing the path from the root to the label in the zigzag tree.
Best Case: O(log(label))
Average Case: O(log(label))
Worst Case: O(log(label))
Description: The time complexity is logarithmic in terms of the label, as we are tracing the path back from the node to the root.
Best Case: O(log(label))
Worst Case: O(log(label))
Description: The space complexity is also logarithmic because we store the path from the root to the node, which depends on the level of the node.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus