Binary Tree Vertical Order Traversal


  • 0

    '''
    public class Solution {
    public int NodeNumbers(TreeNode r)
    {
    if (r == null) return 0;
    return( 1 + (NodeNumbers(r.left)) + (NodeNumbers(r.right)));
    }

    public IList<IList<int>> VerticalOrder(TreeNode root)
    {
        int num = NodeNumbers(root);
        IList<IList<int>> res= new List<IList<int>>(num);
    
        if (root ==null ) return(res);
    
        Dictionary<TreeNode, int> dic = new Dictionary<TreeNode,int>();
        Hashtable ht = new Hashtable();
      
    
        dic.Add(root, 0);      
        Queue<TreeNode> q = new Queue<TreeNode>(num);
        q.Enqueue(root);
    
        while (q.Count > 0)
        {
            TreeNode t =q.Dequeue();
    
            if (t.left != null)
            {
                q.Enqueue(t.left);
                dic.Add(t.left,dic[t]+1);
            }
            if (t.right != null)
            {
                q.Enqueue(t.right);
                dic.Add(t.right, dic[t] - 1);
            }
        }
    
        int max = 0;int min=0;
        foreach (KeyValuePair<TreeNode, int> t in dic)
        {
            if (t.Value > max) max = t.Value;
            if (t.Value < min) min = t.Value;
            List<int> li = new List<int>();
    
            if (ht.ContainsKey(t.Value))
            {
                li = (List<int>)ht[t.Value];
    
            }
            li.Add(t.Key.val);
            ht[t.Value] = li;
        }
    
        for (int i = max; i > min-1; i--)
            res.Add((List<int>)ht[i]);   
        return res;
    }
    

    }
    '''


Log in to reply
 

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