20190503-相同的樹

相同的樹

難度分類

簡單

題目描述

給定兩個二叉樹，編寫一個函數來檢驗它們是否相同。

如果兩個樹在結構上相同，並且節點具有相同的值，則認為它們是相同的。

示例 1:

輸入:       1         1

          / \       / \

         2   3     2   3

        [1,2,3],   [1,2,3]

輸出: true

示例 2:

輸入:      1          1

          /           \

         2             2

        [1,2],     [1,null,2]

輸出: false

示例 3:

輸入:       1         1

          / \       / \

         2   1     1   2

        [1,2,1],   [1,1,2]

輸出: false

演算法

採用層序遍歷只要結構或值不相等就返回False，使用遞歸解該題具體思路如下：

1. 遞歸的結束條件：當比較的treeNode的值都為None的時候返回True
2. 遞歸條件：比較2個treeNode的val,當val相等的時候比較2個TreeNode的左子樹和右子樹

考點

1. 遞歸
2. And運算

代碼

def isSameTree(p, q):
    if p is None and q is None:
        return True
    else:
        if p and q:
            if p.val == q.val:#判斷當前樹節點的值是否相等
                return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
            else:
                return False#如果不相等，則返回False
        else:
            return False

 附：非遞歸代碼

def isSameTree(p,q):
    a = p
    b = q
    while p and q:
        if p.val == q.val:
            p = p.left
            q = q.left
        else:
            return False
    while a and b:
        if p.val == q.val:
            p = p.right
            q = q.right
        else:
            return False
    if p or p or a or b:
        return False
    return True