Java Easy O(n) solution with comments & explanation.


  • 0
    A
    public class Solution {
        public TreeNode addOneRow(TreeNode root, int v, int d) {
            /*
             * if d==1, then new TreeNode needs to be inserted at the root, 
             * so create a new TreeNode and assign existing root to newNode's left.
             */
            if(d==1){ 
                TreeNode newNode = new TreeNode(v);
                newNode.left = root;
                root = newNode;
            }else
                /*
                 * if d>=2, then new TreeNode needs to be inserted after traversal of root, 
                 * so d-2 is passed to Helper function, which will be further compared.
                 */
                addOneRowHelper(root, v, d-2);
            return root;
        }
        public void addOneRowHelper(TreeNode root, int v, int d){
            if(root==null) return;
            if(d==0) {
                    /*
                     * Case d ==0 (original d==2, as d-2 is passed to helper), then TreeNode 
                     *            has to be inserted after root.
                     * Case d > 0 (original d>2, as d-2 is passed to helper), then TreeNode 
                     *            has to be inserted at a particular level.
                     * Logic : save the left child of the root, insert TreeNode with value v  
                     *         and insert the saved left right to left side of the new TreeNode.
                     *         Follow for right child of the root.
                     */
                    TreeNode lChild = root.left;
                    root.left = new TreeNode(v);
                    root.left.left = lChild;
                
                    TreeNode rChild = root.right;
                    root.right = new TreeNode(v);
                    root.right.right = rChild;
            }
            /*
             * Post Order traversal
             */
            addOneRowHelper(root.left, v, d-1);
            addOneRowHelper(root.right, v, d-1);
        }
    }

Log in to reply
 

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