100. Same Tree [easy] (Python)

NO IMAGE

題目連結

https://leetcode.com/problems/same-tree/

題目原文

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

題目翻譯

給定兩個二叉樹,寫個函式判斷它們是否相等。
兩個二叉樹相等指的是,它們結構相同,每個對應節點的值相同。

思路方法

這個問題與遍歷二叉樹的問題很像,因為要比較兩棵樹是否相等,本質上還是要遍歷這兩棵樹,不過當找到兩棵樹的不同時就可以停止了。

思路一

遞迴,實際上相當於同時對兩棵樹進行深度優先遍歷(DFS)。在任一非空節點應該判斷是否值相等且兩棵子樹也相等。

程式碼

# 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 p and q:
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return p == q

思路二

非遞迴的演算法,類似遍歷二叉樹,容易想到用棧。用棧來處理時,可以用兩個棧分別記錄兩棵樹,也可以用一個棧同時記錄兩棵樹。比如,下面的程式碼只用了一個棧。

程式碼

# 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
"""
stack = [(p, q)]
while stack:
p, q = stack.pop()
if p == None and q == None:
continue
if p == None or q == None:
return False
if p.val == q.val:
stack.append((p.right, q.right))
stack.append((p.left, q.left))
else:
return False
return True

思路三

非遞迴除了用棧,也可以用佇列。自然的,廣度優先搜尋(BFS)也是可以的,下面的程式碼同樣是同時記錄兩個樹的資訊到一個佇列裡。

程式碼

# 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
"""
queue = [(p, q)]
while len(queue) != 0:
p, q = queue.pop()
if p == None and q == None:
continue
if p == None or q == None:
return False
if p.val == q.val:
queue.insert(0, (p.left, q.left))
queue.insert(0, (p.right, q.right))
else:
return False
return True

PS: 新手刷LeetCode,新手寫部落格,寫錯了或者寫的不清楚還請幫忙指出,謝謝!
轉載請註明:http://blog.csdn.net/coder_orz/article/details/51399234