CodingMan.cc

LeetCode 筆記 - 617. Merge Two Binary Trees

解析如何合併兩棵二元樹。本文採用深度優先搜尋（DFS）同步走訪兩棵樹，將重疊節點的數值相加，並靈活處理單側存在的子樹結構。這是一篇掌握樹狀結構走訪與動態合併邏輯的基礎開發心得。

發佈
閱讀
約 1 分鐘
字數
274
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

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

也許你也會想看看

輸入關鍵字開始搜尋 · ↑↓ 選擇 · Enter 開啟