Same Tree

題目
思路：

先用以樹來說較直觀的遞迴解

要比較所有相同位置的 node 的值是否一樣，可以把所有待比較的 node pair 丟到 stack 裡一一拿出來比較，全部比完都通過的話就是一樣的 tree
一個 pair 比較後會把下面的所有分支點繼續丟進 stack 等待比較，所以用 while stack: 只要有就繼續比，一直比到完
- 此為廣先搜尋 (Breadth-First Search)

Python3 solution:

# 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
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    stack = [(p, q)]
    while stack:
        p, q = stack.pop()
        if p and q and p.val == q.val:
            stack.extend([
                (p.left, q.left),
                (p.right, q.right)
            ])
        elif p or q:  # 只有在 p, q 都是 None 的情況下才會通過，這代表這兩棵樹在那個位置都沒有葉子
            return False
    return True

假設 p 有 n 個節點，寬度 w1，q 有 m 個節點，寬度 w2

時間複雜度：O(max(m, n))
空間複雜度：O(max(w1, w2))
- 因為是 BFS, stack 需儲存當前層次上的節點，故跟寬度成正比

類似題：Symmetric Tree 用 iterative 方法來解

Same Tree

評論

分類

標籤雲

最新文章

彙整

標籤

最新文章

彙整

標籤

Your browser is out-of-date!