Simple Java solution - O(N)


  • 4

    Simply traverse recursively to the depth d - 1 and add nodes accordingly.

    
    public class Solution {
    	public TreeNode addOneRow(TreeNode root, int v, int d) {
    		if (d == 1) {
    			TreeNode newRoot = new TreeNode(v);
    			newRoot.left = root;
    			return newRoot;
    		}
    		add(root, v, d, 1);
    		return root;
    	}
    
    	private void add(TreeNode node, int v, int d, int currentDepth) {
    		if (node == null) {
    			return;
    		}
    
    		if (currentDepth == d - 1) {
    			TreeNode temp = node.left;
    			node.left = new TreeNode(v);
    			node.left.left = temp;
    
    			temp = node.right;
    			node.right = new TreeNode(v);
    			node.right.right = temp;
    			return;
    		}
    
    		add(node.left, v, d, currentDepth + 1);
    		add(node.right, v, d, currentDepth + 1);
    	}
    }
    
    

  • 1

    Almost the same as my solution, except the null check can be put before put a new layer into the stack, in this way, the stack can save a bout half. This is very useful when the tree is very big.

    public TreeNode addOneRow(TreeNode root, int v, int d) {
        if(d == 1) {
            TreeNode newRoot = new TreeNode(v);
            newRoot.left = root;
            return newRoot;
        }
        addSubNodes(root,v,d,2);
        return root;
    }
    private static void addSubNodes(TreeNode root, int v, int d, int p) {
        if(d == p) {
            TreeNode newLeft = new TreeNode(v);
            TreeNode newRight = new TreeNode(v);
            newLeft.left = root.left;
            root.left = newLeft;
            newRight.right = root.right;
            root.right = newRight;
            return;
        }
        if(root.left != null)//put null check here to avoid 1/2 stack.
        addSubNodes(root.left,v,d,p+1);
        if(root.right != null)
        addSubNodes(root.right,v,d,p+1);
    }

  • 1

    @Felomeng
    The position of the null checks that you have shown will not save half the stack. It would save 1 call stack entry per null node. At any given time there can be only 1 extra node inserted by my null checks. There will be a total of ~ 2*N extra nodes inserted if there are N' nodes with children = null over the course of the algorithm.
    Nonetheless, your checks do save the additional time required to allocate a stack entry for an add call with a null node. Thanks for the insight, really made me think about my solution! :)


  • 0
    A

    @Felomeng But even if left child is null but the depth matches, new node should be created and its respective left or right child should be set to null. I don't get the reason of checking for null? Or may be i have missed something, Thanks :)


  • 0
    Z

    Thanks for the nice solution! Here is mine in C++.

    class Solution {
    public:
        TreeNode* addOneRow(TreeNode* root, int v, int d) {
            if (d == 1) {
                TreeNode *p = new TreeNode(v);
                p->left = root;
                return p;
            }
            dfs(root, v, d-1);
            return root;
        }
    private:
        void dfs(TreeNode* p, int v, int d) {
            if (p == nullptr) return;
            if (d == 1) {
                TreeNode *pl = new TreeNode(v), *pr = new TreeNode(v);
                pl->left = p->left;
                pr->right = p->right;
                p->left = pl;
                p->right = pr;
            }
            else {
               dfs(p->left, v, d-1);
               dfs(p->right, v, d-1);
            }
        }
    };
    

  • 0
    J
    This post is deleted!

Log in to reply
 

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