Recursive solution, beat 77% of java submissions.


  • 0
    J

    Using recursion.

    1. if d=1, simple add at the root.
    2. if d=2, add node v, and link v to root's left and right child if exist.
    3. if d>=3, recursively solve the problem.
    class Solution {
        public TreeNode addOneRow(TreeNode root, int v, int d) {
            if (d==1) {
                TreeNode head = new TreeNode(v);
                head.left=root; 
                return head; 
            }
            else if (d==2) {
                if (root.left!=null) {
                    TreeNode l = root.left;
                    TreeNode x = new TreeNode(v);
                    root.left = x; 
                    x.left = l; 
                }
                else {
                    TreeNode x = new TreeNode(v);
                    root.left = x; 
                }
                
                if (root.right!=null) {
                    TreeNode r = root.right;
                    TreeNode x = new TreeNode(v);
                    root.right = x; 
                    x.right = r; 
                }
                else {
                    TreeNode x = new TreeNode(v);
                    root.right = x;
                }
                return root;
            }
            else {
                if (root.left!=null)
                    addOneRow(root.left, v, d-1);
                if (root.right!=null)
                    addOneRow(root.right, v, d-1);
                return root; 
            }
        }
    }
    

Log in to reply
 

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