項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Leetcode】python – [572] Subtree of Another Tree 個人解法筆記

題目出處

572. Subtree of Another Tree

難度

easy

個人範例程式碼

# 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 isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        # end of recursion
        if not root:
            return False

        # define
        if self.is_same_tree(root, subRoot):
            return True

        # split
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    def is_same_tree(self, root, subroot):
        # end of recursion
        if not root and not subroot:
            return True

        if not root or not subroot: # only one side left
            return False

        if root.val != subroot.val: 
            return False

        return self.is_same_tree(root.left, subroot.left) and self.is_same_tree(root.right, subroot.right)

算法說明

原本的 is_sub_tree,就已經可以幫助我們把大題目拆成小題目了,
我們只需要再多補上一個,比較兩個 tree 是否相同的函數即可。

input handling

if not root,return False (上層只要有一次 True 即可,因此用 or 比較其他答案)

Boundary conditions

用 not root,來判斷 Tree 的結尾。

Reference

⭐ Leetcode 解題紀錄 ⭐題型資料結構Python SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102Binary Tree Level Order TraversalBFS (分層)TreePython
103Binary Tree Zigzag Level Order TraversalBFS (分層)TreePython
107Binary Tree Level Order Traversal IIBFS (分層)TreePython
133Clone GraphBFS (分層)GraphPython Graph 的基本操作 #重要題型
127Word LadderBFS (分層), DFSGraphPython
[Lint] 127Topological SortingBFS (拓撲)Python
內有 indegree, outdegree 介紹 #重要題型
207Course ScheduleBFS (拓樸)GraphPython
210Course Schedule IIBFS (拓樸)GraphPython
[Lint] 892Alien DictionaryBFS (拓樸)GraphPython
[Lint] 431Connected Component in Undirected GraphBFS (連通塊)GraphPython 內含 BFS 模板 #重要題型