LeetCode解題之Same Tree

原題

判斷兩棵二叉樹是否相等。兩棵二叉樹僅在它們的形狀相同且每個節點的值相等時才判為相等。

注意點：

例子：

輸入:

      2           2
p =  / \    q =  / \
    1   3       1   3

輸出: True

解題思路

樹相關的問題一般用遞歸的方法最好理解。如果兩棵樹對應的節點都為空，則相等；如果值相等，那麼就分別判斷它們的左右子樹是否相等，否則認為兩棵樹不相等。

AC源碼

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if not q and not p:
            return True
        elif not p or not q:
            return False
        elif p.val != q.val:
            return False
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)


if __name__ == "__main__":
    None