Simple Java recursive solution - O(n)


  • 1
    public class Solution {
        public TreeNode merge(TreeNode t1, TreeNode t2) {
            if(t1 == null && t2 == null) {
                return null;
            }
            
            TreeNode newNode = new TreeNode(-1);
            if(t1 == null) {
                newNode.val = t2.val;
                newNode.left = merge(null, t2.left);
                newNode.right = merge(null, t2.right);
            }
            else if(t2 == null) {
                newNode.val = t1.val;
                newNode.left = merge(t1.left, null);
                newNode.right = merge(t1.right, null);
            }
            else {
                newNode.val = t1.val + t2.val;
                newNode.left = merge(t1.left, t2.left);
                newNode.right = merge(t1.right, t2.right);
            }
            
            return newNode;
        }
    }
    

  • 0
    F

    Why is this line needed?

    TreeNode newNode = new TreeNode(-1);

    I was reusing t1 here but otherwise had the same code and the new nodes were not getting created. But the sums were working correctly


  • 1

    @FrankUnderwood
    The question exclusively demanded "You need to merge them into a new binary tree." That is why I created the new node


  • 0
    K

    @soumyadeep2007 what do you mean by TreeNode(-1), I didn't find the constructor of the TreeNode


  • 1

    @KyleGaoShijie This is the definition for a TreeNode which is a LeetCode supplied type:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    

Log in to reply
 

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