Java Solution with explanation O(n+m)


  • 0
    F

    Explanation:
    This is a straightforward tree traversal problem. Recursion is used to resolve the problem. The key here is to build the new tree based on 3 scenarios:
    1.Both TreeNode t1 and t2 are null: base case, return null TreeNode
    2.Both TreeNode t1 and t2 are not null: set the new TreeNode curr to the sum of t1 and t2, then recursively find curr.left and curr.right
    3.Either TreeNode t1 or t2 is null: set the new TreeNode curr to either val of t1 or t2, then recursively find curr.left and curr.right
    Big O:
    The Big O is O(n+m), where n is the size of TreeNode t1 and m is the size of TreeNode t2, as both trees have to be traversed to generate the new tree. The big O then can be further generalized as O(n) or O(m), depending on if t1 or t2 is the larger tree

    public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        TreeNode curr = new TreeNode(0); //initialize tree node
            if(t1==null && t2==null){
                curr = null;
            }
            else if(t1!=null && t2!=null){
                curr.val = t1.val + t2.val;
                curr.left = mergeTrees(t1.left, t2.left);
                curr.right = mergeTrees(t1.right, t2.right);
            }
            else{   //case where either t1==null or t2 == null
                curr.val = (t1==null)?t2.val:t1.val;
                curr.left = (t1==null)?mergeTrees(null, t2.left):mergeTrees(t1.left, null);
                curr.right = (t1==null)?mergeTrees(null, t2.right):mergeTrees(t1.right, null);
            }
            return curr;
        }
    }
    

Log in to reply
 

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