100. Same Tree

Question: Same Tree
Solution bottom up DFS

想法：

如果 root (p & q) 相同時，再檢查他們的 left & right 是否相同
比較兩顆樹是否相同 → 先比 root → 比 left subtree → 比 right subtree → preorder traversal

1. recursion 要先定義好：

   1. 終止條件

      如果走到 leaf，兩者 node 都 == None 時，return True

      其中一個 node == None，另一個 node ≠ None 時， return False

   2. 呼叫自己的方式

      • root 相同: if p.val == q.val:

        檢查 children 是否相同：

        • left_same = isSameTree(p.left, q.left)
        • right_same = isSameTree(p.right, q.right)

        return left_same and right_same

      • root 不同時，直接 return False

Time complexity: O(p + q)

# 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:

if p == None and q == None:

return True

elif p == None or q == None:

return False

if p.val == q.val:

left_same = self.isSameTree(p.left, q.left)

right_same = self.isSameTree(p.right, q.right)

return left_same and right_same

return False

Neetcode 標準寫法

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 or (p.val != q.val):

return False

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

Video Solution