123 - 617 合并二叉树

题目

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入: Tree 1 Tree 2 1 2 / / \ 3 2 1 3 / \ 5 4 7

输出: 合并后的树: 3 / 4 5 / 5 4 7

注意: 合并必须从两个树的根节点开始。

解答

感觉需要遍历两个二叉树，同时新建一个新的二叉树

看了题解之后发现，并不用那么麻烦，只需要递归修改t1就行了

https://leetcode-cn.com/problems/merge-two-binary-trees/solution/hen-jian-dan-de-di-gui-c-by-pu-shang-qing-feng/

var mergeTrees = function(t1, t2) {
  if (!t1 && !t2) {
    return null
  }
  if (!t1) {
    return t2
  }
  if (!t2) {
    return t1
  }
  t1.val += t2.val
  t1.left = mergeTrees(t1.left, t2.left)
  t1.right = mergeTrees(t1.right, t2.right)
  return t1
};

Runtime: 104 ms, faster than 12.56% of JavaScript online submissions for Merge Two Binary Trees.

Memory Usage: 40.2 MB, less than 84.62% of JavaScript online submissions for Merge Two Binary Trees.

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if t1 is None and t2 is None:
            return None
        if t1 is None:
            return t2
        if t2 is None:
            return t1
        t1.val += t2.val
        t1.left = self.mergeTrees(t1.left, t2.left)
        t1.right = self.mergeTrees(t1.right, t2.right)
        return t1

Runtime: 84 ms, faster than 87.65% of Python3 online submissions for Merge Two Binary Trees.

Memory Usage: 14.3 MB, less than 20.00% of Python3 online submissions for Merge Two Binary Trees.

python里面没有null，只用None，而且判断的方法几乎就是英文。。😂😂

func mergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {
    if t1 == nil && t2 == nil {
        return nil
    }
    if t1 == nil {
        return t2
    }
    if t2 == nil {
        return t1
    }
    t1.Val += t2.Val
    t1.Left = mergeTrees(t1.Left, t2.Left)
    t1.Right = mergeTrees(t1.Right, t2.Right)
    return t1
}

Runtime: 28 ms, faster than 88.85% of Go online submissions for Merge Two Binary Trees.

Memory Usage: 8.8 MB, less than 100.00% of Go online submissions for Merge Two Binary Trees.