Java Level Order Traversal Solution


  • 0
    T
    public static List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(root==null)
        	return result;
        Hashtable<TreeNode, Integer> ht = new Hashtable<TreeNode, Integer>();
        int col= 0;
        ht.put(root, col);
        Queue<TreeNode> qu = new LinkedList<TreeNode>();
        Queue<TreeNode> next = new LinkedList<TreeNode>();
        qu.add(root);
        int add = 0;
        while(!qu.isEmpty()){
        	TreeNode curr = qu.poll();
        	int curr_col = ht.get(curr);
        	if(curr_col==-1){
        		result.add(0,new ArrayList<Integer>());
        		add =1;
        	}else if(curr_col+add>=result.size()){
        		result.add(new ArrayList<Integer>());
        	}
        	result.get(curr_col+add).add(curr.val);
        	
        	if(curr.left!=null){
        		next.add(curr.left);
        		ht.put(curr.left, curr_col+add-1);
        	}
        	if(curr.right!=null){
        		next.add(curr.right);
        		ht.put(curr.right, curr_col+add+1);
        	}
        	
        	if(qu.isEmpty()){
        		Queue<TreeNode> tmp = qu;
        		qu = next;
        		next = tmp;
        		add = 0;
        	}
        }
        return result;
    }

Log in to reply
 

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