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.


  • 0
    D

    I didn't understand in the recursive approach when we are returning t1 or t2 while checking the null value than the program would stop after that step and the whole addition process will not take place than how it would traverse whole tree if any node is null in anyone of the tree.


  • 0
    L

    Maybe this is what the question is asking for? To store the result in a new tree
    class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    TreeNode root = new TreeNode(0);
    return mergeTrees(root, t1, t2);
    }
    private TreeNode mergeTrees(TreeNode root, TreeNode t1, TreeNode t2) {
    if (t1 == null) {
    root = t2;
    } else if (t2 == null) {
    root = t1;
    } else {
    root.val = t1.val + t2.val;
    if (t1.left != null || t2.left != null) {
    root.left = new TreeNode(0);
    root.left = mergeTrees(root.left, t1.left, t2.left);
    }
    if (t1.right != null || t2.right != null) {
    root.right = new TreeNode(0);
    root.right = mergeTrees(root.right, t1.right, t2.right);
    }
    }
    return root;
    }
    }


  • 0
    S

    @denim_demon912 cuz when t1 or t2 = null, the nodes under it does not need to be merged (tree nodes must be connected), and we can simply connect that part to t1.


Log in to reply
 

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