BFS with nesting calculation


  • 0
    A

    Assume root has nesting 0. For each node except root , it's nesting will be parent's nesting - 1 if it's a left child and parent's nesting + 1 if it's right child.

    Run a BFS to traverse the nodes level wise.

    • For each node, calculate it's nesting.
    • For each nesting, maintain a list of node values having the same nesting. Calculate min and max nesting also.

    Iterate from min nesting to max nesting and collect all the lists associated with each nesting.

    private static class NodeNesting {
    	private final TreeNode node;
    	private final int nesting;
    
    	public NodeNesting(final TreeNode node, final int nesting) {
    		this.node = node;
    		this.nesting = nesting;
    	}
    }
    
    public List<List<Integer>> verticalOrder(final TreeNode root) {
    	if (root == null) {
    		return Collections.emptyList();
    	}
    
    	Map<Integer, List<Integer>> nestingValueMap = new HashMap<>();
    	Queue<NodeNesting> queue = new LinkedList<>();
    	int minNesting = Integer.MAX_VALUE, maxNesting = Integer.MIN_VALUE;
    
    	queue.offer(new NodeNesting(root, 0));
    
    	while (!queue.isEmpty()) {
    		int totalCurrentLevel = queue.size();
    
    		for (int i = 0; i < totalCurrentLevel; i++) {
    			NodeNesting current = queue.poll();
    			TreeNode node = current.node;
    			int nesting = current.nesting;
    
    			List<Integer> values = nestingValueMap.getOrDefault(nesting, new ArrayList<>());
    			values.add(node.val);
    			nestingValueMap.put(nesting, values);
    
    			minNesting = Math.min(minNesting, nesting);
    			maxNesting = Math.max(maxNesting, nesting);
    
    			if (node.left != null) {
    				queue.offer(new NodeNesting(node.left, nesting-1));
    			}
    
    			if (node.right != null) {
    				queue.offer(new NodeNesting(node.right, nesting+1));
    			}
    		}
    	}
    
    	List<List<Integer>> result = new ArrayList<>();
    	for (int nesting = minNesting; nesting <= maxNesting; nesting++) {
    		result.add(nestingValueMap.get(nesting));
    	}
    
    	return result;
    }
    

Log in to reply
 

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