Java BFS


  • 0
    M
            private class Node{
    		TreeNode node;
    		int base;
    		public Node(TreeNode node, int base) {
    			this.node = node;
    			this.base = base;
    		}
    	}
    	public List<List<Integer>> verticalOrder(TreeNode root) {
    		List<List<Integer>> lists = new ArrayList<>();
    		if (root == null) return lists;
    		Map<Integer, List<Integer>> map = new HashMap<>();
    		int min = 0;
    		Queue<Node> q = new LinkedList<>();
    		q.offer(new Node(root, 0));
    		while (!q.isEmpty()) {
    			Node node = q.poll();
    			if (!map.containsKey(node.base)) {
    				map.put(node.base, new ArrayList<>());
    				min = Math.min(min, node.base);
    			}
    			map.get(node.base).add(node.node.val);
    			if (node.node.left != null) q.offer(new Node(node.node.left, node.base - 1));
    			if (node.node.right != null) q.offer(new Node(node.node.right, node.base + 1));
    		}
    		int n = map.size();
    		for (int i = min; i < min + n; ++i) {
    			lists.add(map.get(i));
    		}
    		return lists;
        }
    

Log in to reply
 

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