題目

https://leetcode.com/problems/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:

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.

解答

C#

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

        TreeNode result = new TreeNode(t1.val + t2.val);

        result.left = MergeTrees(t1.left, t2.left);
        result.right = MergeTrees(t1.right, t2.right);
        return result;
    }
}

結果

Runtime: 116 ms, faster than 90.16% of C# online submissions.

Memory Usage: 26.8 MB, less than 14.29% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(n)

為什麼我要這樣做？

今天快到 Tree 的尾聲了，還沒跟上的同學記得要參考之前的文章唷 ↓
[Day 22] 演算法刷題 LeetCode 101. Symmetric Tree (Easy) Part 1 - Recursion
[Day 23] 演算法刷題 LeetCode 101. Symmetric Tree (Eas
y) Part 2 - Iteration
[Day 24] 演算法刷題 LeetCode 104. Maximum Depth of Binary Tree (Easy)
[Day 25] 演算法刷題 LeetCode 543. Diameter of Binary Tree (Easy)
[Day 26] 演算法刷題 LeetCode 226. Invert Binary Tree (Easy)

1. 當 t1 及 t2 同時為 null 時，回傳 null
2. 當 t1 為 null，t2 不為 null 時，回傳 t2
3. 當 t2 為 null，t1 不為 null 時，回傳 t1
4. 宣告一個 node 為 result，其起始值為 t1.val + t2.val
5. result.left 呼叫自己本身的 method MergeTrees 去判斷 下兩個節點的 left
6. result.right 呼叫自己本身的 method MergeTrees 去判斷下兩個節點的 right
7. 回傳 result 直到整個遞迴結束

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉