Java BFS


  • 0
    A
    public class Solution {
    public TreeNode addOneRow(TreeNode root, int v, int d) {
        // algorithm 2017/06/19: queue-based BFS might be a better idea to find depth level
        // the following queue-based algo cannot deal with the case d=1
        if (1 == d) {
            TreeNode newRoot = new TreeNode(v);
            newRoot.left     = root;
            return newRoot;
        }
        
        // the following works if d in range [2, maximum depth of the given tree + 1]
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        
        while(!queue.isEmpty()) {
            depth++;
            int countNodesInLevel = queue.size();
            
            if (depth == d-1) {
                // for each node in this level, create two new nodes
                for (int index = 0; index < countNodesInLevel; index++) {
                    TreeNode nodeInLevel = queue.poll();
                    
                    TreeNode newNode1    = new TreeNode(v);
                    newNode1.left        = nodeInLevel.left;
                    
                    TreeNode newNode2    = new TreeNode(v);
                    newNode2.right       = nodeInLevel.right;
                    
                    nodeInLevel.left     = newNode1;
                    nodeInLevel.right    = newNode2;
                }
                return root;
            } else {
                for (int index = 0; index < countNodesInLevel; index++) {
                    TreeNode nodeInLevel = queue.poll();
                    if (null != nodeInLevel.left) queue.offer(nodeInLevel.left);
                    if (null != nodeInLevel.right) queue.offer(nodeInLevel.right);
                }
            }
        }
        return root;
    }
    

    }


Log in to reply
 

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