基礎圖論題目 Same Tree_Leetcode #100

題目敘述: 100. Same Tree

題目會給定兩棵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)。

Reference:

[1] Python/JS/Go/C++ O(n) sol by DFS [w/ Visualization ] — Same Tree — LeetCode