Leetcode discuss: 1104. Path In Zigzag Labelled Binary Tree

July 18, 2022

Here is the link. 

C# | Quick learner | Apply math analysis

July 18, 2022
It is a very good practice to warmup my math analysis skill. I choose to study one of C# discuss posts, and learn the idea to solve the path from root to given node without constructing a binary tree.

Example

I will think about again and figure out how to calculate the parent node's value based on the above simple example.

1. Calculate current depth of the label
2. Calculate offset (for each depth, values lie from 2^d -> 2^(d+1) -1
3. Find the real parent based on offset
4. Repeat until we reach 1

e.g. parent of 14 is 4

1. depth = 3, values in this depth lie from 8 to 15 (since it is a complete binary tree)
2. offset = 15 - 14 = 1
3. real parent of 14 = parent of ( 8 + offset ) = parent (9) = 9/2 = 4

In a simple statement, to find 14's parent, start from offset 1 to 15 (end), find 8 (start)'s offset 1 -> 9's parent node in non-zigzag order.

The following C# code passes online judge.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1104_zigzag_2
{
    class Program
    {
        static void Main(string[] args)
        {
            var result = PathInZigZagTree(5);
            Debug.Assert(String.Join("-", result).CompareTo("1-3-5") == 0);
        }

        /// <summary>
        /// study code
        /// https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree/discuss/1031053/c
        /// Work on test case - label 5 
        /// </summary>
        /// <param name="label"></param>
        /// <returns></returns>
        public static IList<int> PathInZigZagTree(int label)
        {
            var result = new List<int>();
            var stack = new Stack<int>();

            while (label != 0)
            {
                stack.Push(label);
                label /= 2;
            }

            while (stack.Count > 0)
            {
                result.Add(stack.Pop());
            }

            // result 1->2->5, need to make correction to 1->3->5 
            var count = result.Count;

            for (int i = count % 2 == 0 ? 0 : 1; i < count - 1; i += 2)
            {
                result[i] = (int)Math.Pow(2, i + 1) - 1 - (result[i] - (int)Math.Pow(2, i));
            }

            return result;
        }
    }
}