行前提要

關於之前面試的題目，當下沒能成功寫出來，僅能嘗試說出想法交流
畢竟接觸到的演算法也好刷題也好，我還太淺，就來筆記學習看看到底怎麼一回事

Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
這個問題要求判斷兩棵二叉樹是否相同。
需要比較兩棵樹的結構和節點值是否完全相同。

Input: p = [1,2,3], q = [1,2,3]
Output: true

Input: p = [1,2,1], q = [1,1,2]
Output: false

# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:   

訊息塊定義了一個名為 TreeNode 的類
該類表示二叉樹的節點。TreeNode 類有三個屬性：val ,left ,right
TreeNode對象 p 和 q 作為輸入參數，然後使用這些對象來比較兩棵樹是否相同。

如果兩個樹結構相同且節點具有相同的值，則認為它們是相同的。
總之就是要寫一個函數來檢查它們是否相同。
一個基本的想法是使用深度優先搜索（DFS）或廣度優先搜索（BFS）
遍歷這兩棵樹，然後在遍歷過程中進行比較。

深度優先搜索（DFS）

是一種常用的樹和圖形遍歷算法，它的主要思想是從起始節點開始，選擇一條路徑一直向下搜索，直到達到最深處，然後再返回並探索其他可能的分支。DFS 可以使用遞歸或類似堆棧的方法實現。

深度優先搜索（DFS）有兩種主要的方法：遞歸法和非遞歸法

• 遞歸法：這是最常見且最直觀的深度優先搜索方法。通過遞歸函數，您可以自然而然地深入搜索樹或圖的節點，直到達到最深處，然後再返回並繼續探索其他分支。遞歸法的優點是簡潔易讀，但對於極深的樹或圖可能導致遞歸堆棧溢出。

• 非遞歸法：為了避免遞歸堆棧溢出的問題，可以使用類似堆棧的數據結構（例如堆棧或類似的容器）來實現深度優先搜索。這種方法通常需要額外的代碼來處理堆棧的推入和彈出操作，但對於大規模的樹或圖來說，它是更穩定和可控的方法。

對於二叉樹的 DFS 遞歸方法，通常使用 遞歸函數 來實現，
它可以很容易地在樹的結構中遞歸地遍歷每個節點。

遞歸方法使用函數來實現，其中函數在自己內部調用自己，以處理更小的子問題，直到達到基本情況（終止條件）並返回結果。

下面是二叉樹的 DFS 遞歸方法的一般步驟：

1. 檢查當前節點是否為空（None）。如果是空節點，則返回（結束遞歸）或執行其他相應的操作。
2. 如果當前節點不是空節點，則執行某些操作，例如檢查節點的值或處理節點的數據。
3. 遞歸調用 DFS 函數以訪問當前節點的左子樹，即 DFS(node.left)。
4. 遞歸調用 DFS 函數以訪問當前節點的右子樹，即 DFS(node.right)。
5. 返回到上一級的遞歸調用。

# 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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # 如果都是None，則相同
        if not p and not q:
            return True
        # 如果其中一個為None，另一個不為None，則不相同
        if not p or not q:
            return False
        # 如果節點值不相等，則不相同
        if p.val != q.val:
            return False
        # 遞歸比較左子樹和右子樹
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)