描述
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.
分析
本质上就是遍历二叉树，递归法很简单，迭代也不难写。时间O(n)，空间平均O(logn)，最坏O(n)。
代码
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if not p or not q:
return p == q
if p.val != q.val:
return False
if not self.isSameTree(p.left, q.left):
return False
if not self.isSameTree(p.right, q.right):
return False
return True
|
迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
ss = []
ss.append((p, q))
while ss:
x, y = ss.pop()
if (not x or not y):
if x == y:
continue
else:
return False
if x.val != y.val:
return False
ss.append((x.right, y.right))
ss.append((x.left, y.left))
return True
|