LeetCode 筆記 - 617. Merge Two Binary Trees

Posted on

題目在此 617. Merge Two Binary Trees

給定兩個 Binary Trees，請合併這兩棵樹

image 51

解題思維

基本思維是使用 Depth First Search

遇到兩棵樹都存在的 node，根據題目就是將兩個 node 數值相加
如果一個有 left，另一個沒有，那就接過去
right 也是一樣

完成 😎

程式碼

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
34
35
36
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        
        if not root1:
            return root2
        if not root2:
            return root1
        
        
        def dfs(tree1, tree2):
            if not tree1 or not tree2:
                return
            
            tree1.val += tree2.val
            
            if tree2.left:
                if not tree1.left:
                    tree1.left = tree2.left
                else:
                    dfs(tree1.left, tree2.left)
                    
            if tree2.right:
                if not tree1.right:
                    tree1.right = tree2.right
                else:
                    dfs(tree1.right, tree2.right)
                
        dfs(root1, root2)
        
        return root1

相關文章