Accepted C# BFS solution (beats 100% of other C# solutions)


  • 0
    D
    1. First traverse tree using DFS to figure out the leftest node in the tree.
    2. Traverse tree again using BFS storing the node and it's order in the queue.
    3. While visiting each node during the BFS, add it's value to a list of list of values using the passed order to figure out which list to add to.
    public class Solution {
    
    	class NodeOrder
    	{
    		public TreeNode node;
    		public int order;		
    	}
    
        public IList<IList<int>> VerticalOrder(TreeNode root) {
            int startingOrder = GetLeftest(root, 0);	
    	List<IList<int>> result = new List<IList<int>>();
    	return VerticalOrder(root, startingOrder);
        }
    
    	private static IList<IList<int>> VerticalOrder(TreeNode root, int startingOrder)
    	{
    		IList<IList<int>> result = new List<IList<int>>();
    		Queue<NodeOrder> queue = new Queue<NodeOrder>();		
    		if (root != null) queue.Enqueue(new NodeOrder {node = root, order = startingOrder});
    		
    		while(queue.Count > 0)
    		{
    			NodeOrder item = queue.Dequeue();
    			
    			if (item.node.left != null) queue.Enqueue(new NodeOrder { node = item.node.left, order = item.order - 1 });
    			if (item.node.right != null) queue.Enqueue(new NodeOrder { node = item.node.right, order = item.order + 1});
    
    			while(result.Count <= item.order)
    			{
    				result.Add(new List<int>());
    			}
    
    			result[item.order].Add(item.node.val);
    		}		
    		return result;
    	}
    
    	private static int GetLeftest(TreeNode node, int order)
    	{
    		if (node == null) return 0;
    		return Math.Max(Math.Max(order, GetLeftest(node.left, order + 1)), GetLeftest(node.right, order - 1));
    	}
    }
    

Log in to reply
 

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