题目：给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
1
2
3
4
5
6
7
|
输入: 1 1
/ /
2 3 2 3
[1,2,3], [1,2,3]
输出: true
|
思路：分别判断左子树和右子树是否相同，注意终止条件
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
class :
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if not p and q or not q and p:
return False
if not p and not q:
return True
if p.val != q.val:
return False
left_is_same = self.isSameTree(p.left, q.left)
right_is_same = self.isSameTree(p.right, q.right)
return left_is_same and right_is_same
tree = TreeNode(3)
left_tree = TreeNode(9)
right_tree = TreeNode(20)
right_tree.left = TreeNode(15)
right_tree.right = TreeNode(7)
tree.left = left_tree
tree.right = right_tree
tree1 = TreeNode(10)
tree1.left = left_tree
tree1.right = right_tree
print(Solution().isSameTree(tree, tree1))
|
近期评论