題目會給定兩棵Binary Tree的根結點,要求我們判斷兩棵樹是否一模一樣。
也就是說,形狀相同,節點的數值也相同。
Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true
Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false
Example 3:
Input: p = [1,2,1], q = [1,1,2]
Output: false
圖論中常見的DFS深度優先探索,或BFS廣度優先探索都可以拿來解這一題。
以直覺度和簡潔度來說,DFS更直覺也更乾淨俐落。
先複習一下DFS的通用模板:
def dfs( parameter ):
# 終止條件
if stop conidtion:
return result
# 通則 general cases
dfs( paramater updated )
return result
通則:
若p和q同時存在,則檢查p 和 q 的節點數值是否相等,並且用同樣的邏輯,遞迴檢查p, q的左子樹,和p, q的右子樹是否相等。
終止條件:
若p和q不是同時存在,則檢查是否 p == q 而且都等於 NULL。
若兩者皆為空Null,則返回True。
若否,則返回False。
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
# stop condition
if not( p and q ):
return p == q
# general case:
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
O(n) 每個節點至多拜訪一次,最多就是拜訪整棵樹。
O(n) 成本耗費在call stack,當輸入的兩棵樹都向左歪斜,或向右歪斜時,深度最深,最多為O(n)。
[1] Python/JS/Go/C++ O(n) sol by DFS [w/ Visualization ] — Same Tree — LeetCode