[LeetCode] 617. Merge Two Binary Trees

原题链接：https://leetcode.com/problems/merge-two-binary-trees/

1. 题目介绍

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

给出两个二叉树，想象一下，你要把其中的一个二叉树覆盖在另一个上面，这样相同位置的节点是不是重合了。
对于这些重合的节点，我们将它们的val值相加，得到一个新的节点来代替它们。
在某个位置上，如果没有节点重合，那就使用原来的节点当作新的节点即可。

Example 1:

2. 解题思路

可以同时遍历这两棵树，每次都遍历同样位置的节点。如果其中一棵树的节点为null，那么该位置的新节点就用另外一棵树同样位置的节点来代替。如果某个位置两棵树都有节点，那么就建一个新的节点，val值取 t1.val + t2.val 的和。

实现代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1 == null){
            return t2;
        }
        if(t2 == null){
            return t1;
        }
        
        TreeNode ans = new TreeNode(t1.val + t2.val);
        ans.left = mergeTrees(t1.left , t2.left );
        ans.right = mergeTrees(t1.right, t2.right);
        return ans;
    }
}

当然，也可以直接在t1的基础上进行修改，不必每次都新建一个节点

实现代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1 == null){
            return t2;
        }
        if(t2 == null){
            return t1;
        }
        
        t1.val = t1.val+t2.val;
        t1.left = mergeTrees(t1.left , t2.left );
        t1.right = mergeTrees(t1.right , t2.right);
        return t1;
    }
}