LeetCode Merge Two Binary Trees 合併兩個二元樹

本篇為LeetCode上演算法的簡單問題，Merge Two Binary Trees。

題目如下：

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.

Example 1:

Input: 
 Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
      3
     / \
    4   5
   / \   \ 
  5   4   7

Note:

The merging process must start from the root nodes of both trees

輸入兩個二元樹，並合併兩個二元樹中每個相對應的結點。

題目給的樹的類別如下：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }

}

此題要用到遞迴的技巧，想法順序如下

1. 若兩個樹都不存在則值接返回空。
2. 若一個存在而另一不存在則直接返回存在的樹，無須合併。
3. 若兩個樹都存在則合併目前節點的值，然後呼叫同個方法，分別合併左子節點及右子節點。
4. 分別將合併好的回傳左右節點放至父節點。

public static TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) {
        return null;
    } else if (t2 == null) {
        return t1;
    } else if (t1 == null) {
        return t2;
    } else {
        TreeNode t = new TreeNode(t1.val + t2.val);
        t.left = mergeTrees(t1.left, t2.left);
        t.right = mergeTrees(t1.right, t2.right);
        return t;
    }

}

或是當一邊的節點不存在時，仍合併兩節點值，但該不存在的節點值設為0。

public static TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) {
        return null;
    }
    TreeNode t = new TreeNode((t1 == null ? 0 : t1.val) + (t2 == null ? 0 : t2.val));
    t.left = mergeTrees((t1 == null ? null : t1.left), (t2 == null ? null : t2.left));
    t.right = mergeTrees((t1 == null ? null : t1.right), (t2 == null ? null : t2.right));

    return t;
}

參考：

• LeetCode Invert Binary Tree 二元樹反轉