LeetCode 100 相同的數(shù)：
給定兩個(gè)二叉樹区赵，編寫一個(gè)函數(shù)來檢驗(yàn)它們是否相同。
如果兩個(gè)樹在結(jié)構(gòu)上相同辩稽，并且節(jié)點(diǎn)具有相同的值惧笛，則認(rèn)為它們是相同的。
解題思路：
- 判斷空集
- 若非空， 判斷當(dāng)前節(jié)點(diǎn)的同時(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ì)稱樹：
給定一個(gè)二叉樹昌渤，檢查它是否是鏡像對(duì)稱的膀息。
例如潜支，二叉樹 [1,2,2,3,4,4,3] 是對(duì)稱的冗酿。
但是下面這個(gè) [1,2,2,null,3,null,3] 則不是鏡像對(duì)稱的:
解題思路
- 判斷空集
- 若非空，與上一題類似弱判，只不過要判斷左子數(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è)輸入樹一次净刮，所以總的運(yùn)行時(shí)間為O(n)淹父，
其中n是樹中結(jié)點(diǎn)的總數(shù)暑认。
3. 空間復(fù)雜度：遞歸調(diào)用的次數(shù)受樹的高度限制蘸际。在最糟糕情況下，
樹是線性的根穷，其高度為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)