Java, three methods, one BFS and two DFS


  • 11
    1. BFS, find the d-1th row and add new children to each of them
        public TreeNode addOneRow(TreeNode root, int v, int d) {
            if (d == 1) {
                TreeNode newroot = new TreeNode(v);
                newroot.left = root;
                return newroot;
            }
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            for (int i = 0; i < d-2; i++) {
                int size = queue.size();
                for (int j = 0; j < size; j++) {
                    TreeNode t = queue.poll();
                    if (t.left != null) queue.add(t.left);
                    if (t.right != null) queue.add(t.right);
                }
            }
            while (!queue.isEmpty()) {
                TreeNode t = queue.poll();
                TreeNode tmp = t.left;
                t.left = new TreeNode(v);
                t.left.left = tmp;
                tmp = t.right;
                t.right = new TreeNode(v);
                t.right.right = tmp;
            }
            return root;
        }
    
    1. DFS, with helper function that knows the current depth of each recursion
        private void dfs(TreeNode root, int depth, int v, int d) {
            if (root == null) return;
            if (depth < d-1) {
                dfs(root.left, depth+1, v, d);
                dfs(root.right, depth+1,v, d);
            } else {
                TreeNode tmp = root.left;
                root.left = new TreeNode(v);
                root.left.left = tmp;
                tmp = root.right;
                root.right = new TreeNode(v);
                root.right.right = tmp;
            }
        }
        public TreeNode addOneRow(TreeNode root, int v, int d) {
            if (d == 1) {
                TreeNode newroot = new TreeNode(v);
                newroot.left = root;
                return newroot;
            }
            dfs(root, 1, v, d);
            return root;
        }
    
    1. DFS without helper function, similar to @alexander 's top post
        public TreeNode addOneRow(TreeNode root, int v, int d) {
            if (d < 2) {
                TreeNode newroot = new TreeNode(v);
                if (d == 0) newroot.right = root;
                else newroot.left = root;
                return newroot;
            }
            if (root == null) return null;
            root.left = addOneRow(root.left, v, d == 2 ? 1 : d-1);
            root.right = addOneRow(root.right, v, d == 2 ? 0 : d-1);
            return root;
        }
    

  • 1
    F

    Thank you for sharing three solutions. Here's my solution, same with your second one. Vote for u!

    public class Solution {
        public TreeNode addOneRow(TreeNode root, int v, int d) {
            if(d == 1){
                TreeNode dummy = new TreeNode(v);
                dummy.left = root;
                return dummy;
            }
            helper(root,v,d,1);
            return root;
        }
        public void helper(TreeNode root,int v, int d, int cur){
            if(root == null) return;
            if(cur == d-1){
                TreeNode temp = new TreeNode(v);
                temp.left = root.left;
                root.left = temp;
                TreeNode temp2 = new TreeNode(v);
                temp2.right = root.right;
                root.right = temp2;
                return;
            }
            helper(root.left,v,d,cur+1);
            helper(root.right,v,d,cur+1);
        }
    }
    

  • 1
    L

    Thank you for your solution! Here's my solution! Same as your second one!

    public class Solution {
        int targetDepth;
        public TreeNode addOneRow(TreeNode root, int v, int d) {
            if (d == 1) {
                //if (root == null) return new TreeNode(v);
                TreeNode newRoot = new TreeNode(v);
                newRoot.left = root;
                return newRoot;
            }
            targetDepth = d;
            inOrderTraverse(root, v, 1);
            return root;
        }
        public void inOrderTraverse(TreeNode root, int v, int currdepth) {
            //reach the d-1 layer
            if (root == null) return;
            if (currdepth == targetDepth - 1) {
                TreeNode newLeft = new TreeNode(v);
                TreeNode newRight = new TreeNode(v);
                newLeft.left = root.left;
                newRight.right = root.right;
                root.left = newLeft;
                root.right = newRight;
                return;
            }
            inOrderTraverse(root.left, v, currdepth+1);
            inOrderTraverse(root.right, v, currdepth+1);
            return;
            
        }
    }
    

  • 0

    Same BFS idea

    public class Solution {
        public TreeNode addOneRow(TreeNode root, int v, int d) {
            if (d == 1) {
                TreeNode res = new TreeNode(v);
                res.left = root;
                return res;
            }
            int depth = 1;
            int queueSize = 1;
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.add(root);
            while (!queue.isEmpty()) {
                if (d - depth == 1) {  //reach targets' parent node
                    for (int i = 0; i < queueSize; i++) {
                        TreeNode curr = queue.remove();
                        TreeNode lnew = new TreeNode(v);
                        lnew.left = curr.left;
                        curr.left = lnew;
                        TreeNode rnew = new TreeNode(v);
                        rnew.right = curr.right;
                        curr.right = rnew;
                    }
                    return root;
                }
                for (int i = 0; i < queueSize; i++) {
                    TreeNode curr = queue.remove();
                    if (curr.left != null) queue.add(curr.left);
                    if (curr.right != null) queue.add(curr.right);
                }
                queueSize = queue.size();
                depth++;
            }
            return root;
        }
    }
    

  • 0
    C

    @jz34
    hi, I have a question concerning this part:
    if (d - depth == 1) { //reach targets' parent node
    for (int i = 0; i < queueSize; i++) {
    TreeNode curr = queue.remove();
    TreeNode lnew = new TreeNode(v);
    lnew.left = curr.left;
    curr.left = lnew;
    TreeNode rnew = new TreeNode(v);
    rnew.right = curr.right;
    curr.right = rnew;
    }
    return root;
    How does your new node curr react to the original counterpart in the tree? I mean, when you create a new node(curr) and make changes to curr, how does these changes influence the the original node in the tree?

    curr is another node but has nothing to do with the original node's parent node, right? how does your code connect curr to its parent node? I am a little confused... Sorry to trouble.


  • 0
    F

    Time flies! After three months later, when I met this question again, I solve it with totally different way. My previous version is DFS, now I solve it with BFS. Just wondering several months later when I met this question again, which method will I use. lol

    class Solution {
        public TreeNode addOneRow(TreeNode root, int v, int d) {
            if (d == 1) {
                TreeNode newRoot = new TreeNode(v);
                newRoot.left = root;
                return newRoot;
            }
            Queue<TreeNode> queue = new LinkedList();
            queue.offer(root);
            int depth = 1;
            while (!queue.isEmpty()) {
                if (depth != d - 1){
                    int size = queue.size();
                    for (int i = 0; i < size; i++){
                        TreeNode node = queue.poll();
                        if (node.left != null) {
                            queue.offer(node.left);
                        }
                        if (node.right != null) {
                            queue.offer(node.right);
                        }
                    }
                    depth++;
                } else {
                    int size = queue.size();
                    for (int i = 0; i < size; i++){
                        TreeNode node = queue.poll();
                        TreeNode newLeft = new TreeNode(v);
                        newLeft.left = node.left;
                        node.left = newLeft;
                        TreeNode newRight = new TreeNode(v);
                        newRight.right = node.right;
                        node.right = newRight;
                    }
                    break;
                }
            }
            return root;
        }
    }
    

Log in to reply
 

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