Easy java solution using level order Traversal which beats 80% of submissions


  • 0
    D
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode addOneRow(TreeNode root, int v, int d) {
            
            
            /*Base case: if d is 1, tree needs a new root node
            if a root was already present, add it as the left subtree
            of the new root node*/
            if(d==1)
            {
                TreeNode newRoot=new TreeNode(v);
                
                if(root!=null)
                    newRoot.left=root;
                
                return newRoot;
            }
            
            /*General case: if 1 or more nodes are present and d is more than 1,
            call a recursive function to do a level order traversal through the tree*/
            levelTraversal(root,1,d,v);
            
            return root;
            
            
        }
        
        public void levelTraversal(TreeNode root,int currentLevel,int finalLevel,int value)
        {
            //Base case: if root is null, return
            if(root==null)
                return;
            
            //General case: if 1 or more nodes are present
            
            /*if currently at one level away from the destination Level, 
              add the new Nodes to the next level in the tree,
              add the left and right subtrees if present and return
              once done
            */
            if(currentLevel==finalLevel-1)
            {
                
                TreeNode leftSubtree=root.left;
                TreeNode rightSubtree=root.right;
                
                TreeNode newLeftNode=new TreeNode(value);
                TreeNode newRightNode=new TreeNode(value);
                
                root.left=newLeftNode;
                newLeftNode.left=leftSubtree;
                    
                root.right=newRightNode;
                newRightNode.right=rightSubtree;
    
                
                return;
            }
            
            //recurse on left and right subtrees
            levelTraversal(root.left,currentLevel+1,finalLevel,value);
            levelTraversal(root.right,currentLevel+1,finalLevel,value);
        }
    }
    

Log in to reply
 

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