100. 相同的樹(shù)
給定兩個(gè)二叉樹(shù)，編寫一個(gè)函數(shù)來(lái)檢驗(yàn)它們是否相同在岂。
如果兩個(gè)樹(shù)在結(jié)構(gòu)上相同奔则，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的蔽午。
示例 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
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/same-tree
普通寫法1：深度優(yōu)先搜索（7行）
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
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)
思路：判斷當(dāng)下節(jié)點(diǎn)是否相同易茬，而后判斷左孩子和右孩子是否相同。如果p和q都是null則當(dāng)下相同；p和q有一個(gè)是null則不同抽莱；否則看二者value是否相同范抓。
普通寫法2：廣度優(yōu)先搜索（17行）
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
def check(p, q):
if not p and not q:
return True
if not q or not p:
return False
if p.val != q.val:
return False
return True
deq = deque([(p, q)])
while deq:
p, q = deq.popleft()
if not check(p, q):
return False
if p:
deq.append((p.left, q.left))
deq.append((p.right, q.right))
return True
思路：用一個(gè)雙邊隊(duì)列將當(dāng)下節(jié)點(diǎn)的孩子放在隊(duì)列里，每次都查看當(dāng)前隊(duì)首是否相同食铐。
大神寫法1：深度優(yōu)先搜索（3行）
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p and q:
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return p is q
思路與普通寫法1一致匕垫。return p is q等價(jià)于return True if p == None and q == None else False。
大神寫法2：廣度優(yōu)先搜索（3行）
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
def t(n):
return n and (n.val, t(n.left), t(n.right))
return t(p) == t(q)
將所有的節(jié)點(diǎn)展成元組的形式虐呻，(root, left, right)象泵。由于and只在前項(xiàng)為真時(shí)返回后項(xiàng)的邏輯值，所以遇到空節(jié)點(diǎn)會(huì)返回空斟叼。
舉例偶惠，如果二叉樹(shù)p的形狀是：
1
/ \
2 3
/
4
print(t(p))返回
(1, (2, (4, None, None), None), (3, None, None))
這里的(n.val, t(n.left), t(n.right))換成[n.val, t(n.left), t(n.right)]也可以。
上帝之手（1行）
def isSameTree(self, p, q):
return p and q and p.val == q.val and all(map(self.isSameTree, (p.left, p.right), (q.left, q.right))) or p is q
思路與深度優(yōu)先搜索一致朗涩。
上述所有寫法的時(shí)間復(fù)雜度（除大神寫法2）都是O(min(m,n))其中m,n表示兩棵樹(shù)的葉子節(jié)點(diǎn)數(shù)忽孽。如果先遍歷兩棵樹(shù)再比較，也包括大神寫法2馋缅，復(fù)雜度是O(max(m,n))扒腕。
