C# - level order traversal - bypass HashTable with find min/max columns


  • 0

    Here is an alternative to using the hash table.
    Spend 1 pass to get min and max column index values, this is two O(n) operations. Then use min and max column index values to initialize your result and you can directly add values to result as you do the level order traversal.

        public IList<IList<int>> VerticalOrder(TreeNode root) 
        {
            IList<IList<int>> lists = new List<IList<int>>();
            if (root == null) return lists;
            
            // determine the column range up front - single pass for each
            int minColIndex = GetMinColIndex(root);
            int maxColIndex = GetMaxColIndex(root);
            
            // init result with empty list for each column
            for (int i = minColIndex; i <= maxColIndex; i++)
            {
                lists.Add(new List<int>());
            }
            
            // level order traversal using 2 queues to hold both node and column index
            Queue<TreeNode> nodeQ = new Queue<TreeNode>();
            Queue<int> colIndexQ = new Queue<int>();
            nodeQ.Enqueue(root);
            colIndexQ.Enqueue(0);
            
            while (nodeQ.Count > 0)
            {
                TreeNode node = nodeQ.Dequeue();
                int col = colIndexQ.Dequeue();
                
                lists[col-minColIndex].Add(node.val);
                if (node.left != null)
                {
                    nodeQ.Enqueue(node.left);
                    colIndexQ.Enqueue(col - 1);
                }
                if (node.right != null)
                {
                    nodeQ.Enqueue(node.right);
                    colIndexQ.Enqueue(col + 1);
                }
            }
            
            return lists;
        }
        
        public int GetMinColIndex(TreeNode node)
        {
            if (node == null) return 0;
            int left = node.left == null ? 0 : -1 + GetMinColIndex(node.left);
            int right = node.right == null ? 0 : 1 + GetMinColIndex(node.right);
            return Math.Min(left, right);
        }
        
        public int GetMaxColIndex(TreeNode node)
        {
            if (node == null) return 0;
            int left = node.left == null ? 0 : -1 + GetMaxColIndex(node.left);
            int right = node.right == null ? 0 : 1 + GetMaxColIndex(node.right);
            return Math.Max(left, right);
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.