LeetCode 相同樹判斷：遞歸法解析

題目描述

判斷兩棵二叉樹是否完全相同：結構相同且對應節點值相等。

遞歸解法

若兩根節點均為空返回真；若一空一非空返回假；值不等返回假；否則遞歸比較左子樹與左子樹、右子樹與右子樹。

class Solution:
    def isSameTree(self, p, q):
        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(min(m, n))，m、n 為兩樹節點數。
• 空間：O(h)，h 為樹高，遞歸棧深度。