Merge Two Binary Trees


  • 1

    Click here to see the full article post


  • 0
    1

    public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if(t1 == null)
    return t2;
    if(t2 == null)
    return t1;
    tl.val = t1.val + t2.val;
    tl.left = mergeTrees(tl.left,t2.left);
    t2.left = mergeTrees(tl.right,t2.right);
    return t1;
    }
    }


  • 0
    B

    t1.val += t2.val;
    How can this be valid? For current case if t1.val == 5 and t2.val == null, after execution t1.val += t2.val, t1.val will be null.
    IMO, t1.val += t2.val should be replaced with (in C#):
    if (t1.val.HasValue && t2.val.HasValue)
    t1.val += t2.val.Value;
    else if (t1.val.HasValue)
    t1.val = t1.val.Value;
    else if (t2.val.HasValue)
    t1.val = t2.val.Value;
    else
    t1.val = null;


  • 0

    @bagram t1.val+=t2.val will execute only when t1!=null and t2!=null.


  • 0
    B

    @vinod23 Here the expected answer is an array of integers [3,4,5,5,4,null,7]. How can int[] have 'null' value? Field 'val' in 'TreeNode' class has type int, not nullable int (int?).


  • 0

    @bagram Here Expected answer is TreeNode i.e. root of the tree. Leetcode represents 'Tree' as an array.
    [3,null,4] is equivalent to

    3
     \
      4

  • 0
    B

    @vinod23 Thank you for explanation. Now I've finally understood.


  • 0
    W
    This post is deleted!

  • 0
    Z

    The problem requirements specify that the merged tree must be in a new binary tree. The iterative method only changes the first tree.


  • 0
    J

    You need to merge them into a new binary tree.

    The problem description is a bit misleading, both solutions mutate one of the trees directly


  • 0
    Y

    Yea the problem expects a new binary tree. The solution is a bit misleading.


  • 0
    H
    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} t1
     * @param {TreeNode} t2
     * @return {TreeNode}
     */
    
    var mergeTrees = function(t1, t2) {
          if(t1 !== null || t2 !== null) {
              var tmp = new TreeNode();
              if(t1 !== null && t1 !== undefined) {
                  tmp.val = t1.val;
              }else{
                  tmp.val= null
              }
              if(t2 !== null) tmp.val += t2.val;
              tmp.left = mergeTrees ((t1 !== null) ? t1.left : null, (t2 !== null) ? t2.left : null);
              tmp.right = mergeTrees ((t1 !== null) ? t1.right : null, (t2 !== null) ? t2.right : null);
              return tmp;
          }
          else return null;
      };
    
    

    我的答案~


  • 0
    H
    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} t1
     * @param {TreeNode} t2
     * @return {TreeNode}
     */
    
    
    var mergeTrees = function(t1, t2) {
          if(t1 !== null || t2 !== null) {
              var tmp = new TreeNode();
              if(t1 !== null && t1 !== undefined) {
                  tmp.val = t1.val;
              }else{
                  tmp.val= null
              }
              if(t2 !== null) tmp.val += t2.val;
              tmp.left = mergeTrees ((t1 !== null) ? t1.left : null, (t2 !== null) ? t2.left : null);
              tmp.right = mergeTrees ((t1 !== null) ? t1.right : null, (t2 !== null) ? t2.right : null);
              return tmp;
          }
          else return null;
      };
    

  • 0
    Y

    @HuangHongRui Even though this works perfectly fine with JS (thanks to type coercion). I still think this should have a comment explaining null + <number> or just change the code so it's clear for non-JS aware folks.

    I would adjust that check to be as simple as:

    ...
    if (t2 !== null) tmp.val = tmp.val === null ? t2.val : tmp.val + t2.val;
    ...
    

  • 0
    F

    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
    if (t1 == NULL && t2 == NULL)
    {
    return NULL;
    }

    	int val = (t1 ? t1->val : 0) + (t2 ? t2->val : 0);
    	TreeNode *ret = new TreeNode(val);
    	ret->left = mergeTrees(t1 ? t1->left : NULL, t2 ? t2->left : t2);
    	ret->right = mergeTrees(t1 ? t1->right : NULL, t2 ? t2->right : t2);
    	return ret;
    }

  • 0

    The check if (t[0] == null || t[1] == null) in the 18th line can actually be simplified to if (t[1] == null).


  • 0
    J

    If you really think about it, Method 2's space complexity is in best-case O(1) in case of t1 being a skewed tree and in worse-case O(n) in case of t1 and t2 both being a balanced tree.


Log in to reply
 

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