# **Leetcode筆記(Same Tree)**

:::info
:information_source: 題目 : Same Tree, 類型 : binary tree , 等級 : easy
日期 : 2023/03/18，2023/05/24，2023/07/05，2023/09/21
:::

### 嘗試

忘記存，原本想用queue。時間複雜度O(n)，空間複雜度O(n)

2023/05/24

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        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))

2023/07/05

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not q and not p:
            return True
        if not q or not p:
            return False
        # 要注意這裡不能比較數字True 不然False會抓不出來
        if q.val != p.val: 
            return False
        
        return (self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right))

2023/09/21

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        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)

---
### **優化**

時間複雜度O(p+q)，空間複雜度O(n)

# 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:
        # 兩個為null
        if not p and not q:
            return True

        # 一個為null
        if not p or not q: 
            return False

        # value不一樣
        if p.val != q.val:
            return False

        # 會走到這步驟的 就是node都存在且value一樣

        return (self.isSameTree(p.left, q.left)) and (self.isSameTree(p.right, q.right))

---

**:warning: 錯誤語法**
:::warning
如果要return A and B(為一個bool)，要把A和B括號起來
:::

**:thumbsup:學習**
:::success
兩個都是null的話算是true
感覺像是這類跌代，都是考慮起始值，跟最後要怎麼停就好
:::

**思路**

**講解連結**
https://www.youtube.com/watch?v=vRbbcKXCxOw
Provided by. NeetCode

###### tags: `binary tree` `easy` `leetcode`