Java iterative BFS


  • 0
    M

    Hi, everyone:
    I just want to share my Java BFS approach, no recursion here.

        public TreeNode addOneRow(TreeNode root, int v, int d) {
            if( d==1 ){
                TreeNode node = new TreeNode(v);
                node.left = root;
                return node;
            }
            
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.add(root);
            int level=1;
            while( q.size()>0 ){
                if( level == d-1 ){
                    while( q.size() > 0 ){
                        TreeNode cur = q.poll();
                        TreeNode left = cur.left;
                        cur.left = new TreeNode(v);
                        cur.left.left = left;
                        
                        TreeNode right = cur.right; 
                        cur.right = new TreeNode(v);
                        cur.right.right = right; 
                    }
                    break;
                }
                
                Queue<TreeNode> temp = new LinkedList<TreeNode>(); 
                while( q.size() > 0 ){
                    TreeNode cur = q.poll();
                    if( cur.left!=null )
                        temp.add(cur.left);
                    if( cur.right!=null )
                        temp.add(cur.right);
                }
                q = temp; 
                level++;
            }
            
            return root;
        }
    }
    

Log in to reply
 

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