LeetCode 100 相同的數(shù)：

給定兩個(gè)二叉樹(shù)，編寫(xiě)一個(gè)函數(shù)來(lái)檢驗(yàn)它們是否相同。
如果兩個(gè)樹(shù)在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的。

解題思路：

1. 判斷空集
2. 若非空， 判斷當(dāng)前節(jié)點(diǎn)的同時(shí)，遞歸樹(shù)的左子數(shù)和右子數(shù)

代碼

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def isSameTree(self, p, q):
        if q is None and p is None:
            return True
        elif q is not None or p is not None:
            return q.val == p.val and self.isSameTree(p.left, q.left) \
                   and self.isSameTree(p.right,  q.right)

LeetCode 101 對(duì)稱(chēng)樹(shù)：

給定一個(gè)二叉樹(shù)，檢查它是否是鏡像對(duì)稱(chēng)的。
例如，二叉樹(shù) [1,2,2,3,4,4,3] 是對(duì)稱(chēng)的。

但是下面這個(gè) [1,2,2,null,3,null,3] 則不是鏡像對(duì)稱(chēng)的:

解題思路

1. 判斷空集
2. 若非空，與上一題類(lèi)似，只不過(guò)要判斷左子數(shù)和右子數(shù)是否相等

代碼

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        1. 時(shí)間復(fù)雜度：O(n)
        2. O(n)，因?yàn)槲覀儽闅v整個(gè)輸入樹(shù)一次，所以總的運(yùn)行時(shí)間為O(n)，
        其中n是樹(shù)中結(jié)點(diǎn)的總數(shù)。
        3. 空間復(fù)雜度：遞歸調(diào)用的次數(shù)受樹(shù)的高度限制。在最糟糕情況下，
        樹(shù)是線(xiàn)性的，其高度為O(n)。
        4. 因此，在最糟糕的情況下，由棧上的遞歸調(diào)用造成的空間復(fù)雜度為O(n)
        """
        root1 = root
        root2 = root
        return self.isMirror(root1, root2)
    def isMirror(self, root1, root2):
        if root1 is None and root2 is None:
            return True
        if root2 is not None and root2 is not None:
            return root1.val == root2.val and self.isMirror(root1.left, root2.right) \
                   and self.isMirror(root1.right, root2.left)