LeetCode 筆記 - 617. Merge Two Binary Trees

題目在此 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

也許你也會想看看