Leetcode discuss: 1104. Path In Zigzag Labelled Binary Tree

 Here is the discussion link. 

Sept. 7, 2020
1104. Path In Zigzag Labelled Binary Tree

Introduction
The problem to find the path from given integer to the root node can be solved using various ways. The easy one I guess can be solved using a few for loops to solve.

My practice
I like to practice the algorithm using a tree algorithm, and also practice the way I think using Stack.
The solution I wrote has "Time Limit Exceeded" bug. But I like to write the solution first, and then learn from my practice.

public class Solution {
    class TreeNode
    {
        public int Val { get; set; }
        public TreeNode left { get; set; }
        public TreeNode right { get; set; }
        public TreeNode(int value)
        {
            Val = value;
        }
    }
    
    public IList<int> PathInZigZagTree(int label) {
        if (label < 1)
            {
                return new List<int>();
            }

            // zigzag traverse the tree level by level, and also build a map
           // with parent node
            var parentMap = new Dictionary<TreeNode, TreeNode>();

            int index = 1;

            // using Queue to apply level by level ordre traversal
            // Tuple<TreeNode, TreeNode> - node, it's parent node
            var stack = new Stack<TreeNode>();
            stack.Push(new TreeNode(index++));

            if(label == 1)
            {
                return new List<int>(new int[] { 1 });
            }
        
            TreeNode found = null;

            while (stack.Count > 0 && index <= label)
            {
                var count = stack.Count;
                var nextLevel = new Stack<TreeNode>(); 

                for (int i = 0; i < count; i++)
                {
                    var root = stack.Pop();

                    // right first, then left
                    for (int j = 0; j < 2; j++)
                    {
                        var child = new TreeNode(index++);

                        nextLevel.Push(child);
                        parentMap.Add(child, root);
                        if (index == label + 1)
                        {
                            found = child;
                        }
                    }
                }

                stack = nextLevel; // maintain the order, do not mix with parent level nodes using standalone stack
            }

            var toRootPath = new Stack<int>();
            while (found != null)
            {
                toRootPath.Push(found.Val);
                if (parentMap.ContainsKey(found))
                {
                    found = parentMap[found];
                }
                else
                {
                    break;
                }
            }

            var list = new List<int>();
            while (toRootPath.Count > 0)
            {
                list.Add(toRootPath.Pop());
            }

            return list;
        }
    }