Java with first BFS O(n)


  • 0
    L
    public class Solution {
        public TreeNode addOneRow(TreeNode root, int v, int d) {
            if(d == 1){
                TreeNode headNode = new TreeNode(v);
                headNode.left = root;
                return headNode;
            }else if(root == null&&d>1){
                return root;
            }
            Queue<TreeNode> queue = new ArrayDeque<>();
            queue.add(root);
            int level = 1;
            while (!queue.isEmpty()){
                int length = queue.size();
                for(int i=0;i<length;i++){
                    TreeNode tmpNode = queue.poll();
                    if(level == d-1){
                        TreeNode newNode = new TreeNode(v);
                        newNode.left = tmpNode.left;
                        tmpNode.left = newNode;
                        TreeNode newNode2 = new TreeNode(v);
                        newNode2.right = tmpNode.right;
                        tmpNode.right = newNode2;
                        
                    }else {
                        if(tmpNode.left!=null) queue.add(tmpNode.left);
                        if(tmpNode.right!=null) queue.add(tmpNode.right);                
                    }
                }
                if(level == d-1){
                    break;
                }
                level++;
            }
            return root;
        }
    }
    

Log in to reply
 

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