C#: Easy to understand solution using BFS with explanation. (Accepted)


  • 0

    0_1523332413102_24ad4404-06df-487e-8d1d-3ebb5a969419-image.png

    public class TreeNode {
    	public int val;
    	public TreeNode left;
    	public TreeNode right;
    	public TreeNode(int x) { val = x; }
    }
    
    public class Solution {
        public IList<IList<int>> VerticalOrder(TreeNode root) {
            IList<IList<int>> res = new List<IList<int>>();
            if (root == null)
                return res;
            int min = 0;           //To track the left most span of the tree.
            int max = 0;          //To track the right most span of the tree.
            Dictionary<int, List<int>> map = new Dictionary<int, List<int>>();  //map vertical level -> nodes.
            Queue<int> orderQueue = new Queue<int>();                     //For BFS to track vertical order (left to right)
            Queue<TreeNode> treeNodesQueue = new Queue<TreeNode>();      //For BFS to track tree nodes.
            treeNodesQueue.Enqueue(root);
            orderQueue.Enqueue(0);
            while (treeNodesQueue.Count > 0) {
                int order = orderQueue.Dequeue();
                TreeNode node = treeNodesQueue.Dequeue();
                List<int> currList;
                if (!map.TryGetValue(order, out currList)) {    //Insert the curr node in the list
                    currList = new List<int>();
                    map[order] = currList;
                }
                currList.Add(node.val);
                if (node.left != null) {                    //Go to Left
                    treeNodesQueue.Enqueue(node.left);
                    orderQueue.Enqueue(order - 1);
                    min = Math.Min(min, order - 1);
                }
                if (node.right != null) {                   //Go to Right
                    treeNodesQueue.Enqueue(node.right);
                    orderQueue.Enqueue(order + 1);
                    max = Math.Max(max, order + 1);
                }
            }
            for (int i = min; i <= max; i++)    //Convert map to result
                res.Add(map[i]);
            return res;        
        }
    }
    

Log in to reply
 

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