Contents

[Golang][Leetcode][BinaryTree]刷題系列-617-Merge Two Binary Trees


617. Merge Two Binary Trees


Level : Easy

原題連結 : Click

題目 :

You are given two binary trees root1 and root2.

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 the two trees 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 the new tree.

Return the merged tree.

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

Example :

Note

Example 1:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] Output: [3,4,5,5,4,null,7]

Example 2:

Input: root1 = [1], root2 = [1,2] Output: [2,2]


解題思路 :

  • 這題的概念可以直接參考 leetcode106題解,一樣是重構binary tree,只是這題直接給你更明確的algorithm,只需要照著他的規範就可以寫出完善的程式
  • 這題雖然是easy,但在思考這題時一不小心思路會卡住
  • 這題需要你做的是合併兩個binary tree,同樣的位置若一個是null,一個不是,將由不是null的直接取代,若同樣位置兩邊都不是null,則值相加後成為新的node
  • 每次遇到這類題目時,都可以先想好第一層邏輯,在用同樣的邏輯寫recursive code
  • 我自己認為需要注意的地方就是,if root1 == nil的部分,這邊並非是直接讓root2.Val去成為新的node的value,而是直接讓root2等於新的node,因為既然root1都已經不存在了,代表同個位置的root2之後往下的path也不用再跟root1去做比對,可以把自該位置的root2直接copy到新的node,為更省事且簡潔。

Recursive解法

  • time complexity: O(n) , space complexity: O(n)

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


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    
    
    if root1 == nil && root2 == nil {
        return nil 
    }
    
    if root1 == nil {
        return root2
    }
    
    if root2 == nil {
        return root1
    }
    
        
    resRoot := &TreeNode {
        Val: root1.Val + root2.Val,
        Left: mergeTrees(root1.Left, root2.Left),
        Right: mergeTrees(root1.Right, root2.Right),
    }
    
    return resRoot
    
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!