【数据结构】树 Tree

1、leetcode100:相同的树

给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Bnode:
'''二叉树的节点'''
def __init__(self, root, left=None, right=None):
self.root = root
self.left = left
self.right = right

def getBTreewithBFS(l):
'''给定二叉树的层序遍历, 重建该二叉树'''
if l[0]:
root = Bnode(l[0])
nodes = [root]
id = 1
while nodes and id < len(l):
node = nodes[0] # 依次为每个节点分配子节点
node.left = Bnode(l[id]) if l[id] else None
nodes.append(node.left)
node.right = Bnode(l[id+1]) if id<len(l)-1 and l[id+1] else None
nodes.append(node.right)
id+=2 # 每次取出两个节点
nodes.pop(0)
return root
else:
return None

def PrintBTree(root):
'''打印二叉树, 从顶到底'''
tmp = []
result = []
if root == None:
return result
tmp.append(root)
while tmp:
newNode = tmp.pop(0)
if newNode == None:
result.append(None)
else:
result.append(newNode.root)
if newNode.left or newNode.right:
tmp.append(newNode.left)
tmp.append(newNode.right)
return result

#################################################################

def isSameTree(p, q):
# 先判断是否全为空,是则返回;再判断是否有一个为空,是则返回,再判断两个值是否相等
if not p and not q:
return True
elif p == None or q == None:
return False
elif p.root != q.root:
return False
return isSameTree(p.left,q.left) and isSameTree(p.right,q.right)

t1 = getBTreewithBFS([1,3,2])
t2 = getBTreewithBFS([1,3,2])
print(isSameTree(t1, t2))

2、leetcode101:对称二叉树

给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Bnode:
'''二叉树的节点'''
def __init__(self, root, left=None, right=None):
self.root = root
self.left = left
self.right = right

def getBTreewithBFS(l):
'''给定二叉树的层序遍历, 重建该二叉树'''
if l[0]:
root = Bnode(l[0])
nodes = [root]
id = 1
while nodes and id < len(l):
node = nodes[0] # 依次为每个节点分配子节点
node.left = Bnode(l[id]) if l[id] else None
nodes.append(node.left)
node.right = Bnode(l[id+1]) if id<len(l)-1 and l[id+1] else None
nodes.append(node.right)
id+=2 # 每次取出两个节点
nodes.pop(0)
return root
else:
return None

def PrintBTree(root):
'''打印二叉树, 从顶到底'''
tmp = []
result = []
if root == None:
return result
tmp.append(root)
while tmp:
newNode = tmp.pop(0)
if newNode == None:
result.append(None)
else:
result.append(newNode.root)
if newNode.left or newNode.right:
tmp.append(newNode.left)
tmp.append(newNode.right)
return result

#################################################################

def isSymmetric(root):
if not root: return True
def match(l, r):
if not l and not r: return True
if not l or not r: return False
return l.root == r.root and match(l.left, r.right) and match(l.right, r.left)
return match(root.left , root.right)

t1 = getBTreewithBFS([1,2,2,3,4,4,3])
t2 = getBTreewithBFS([1,3,2])
print(isSymmetric(t1))
print(isSymmetric(t2))

3、leetcode226:翻转二叉树

翻转一棵二叉树。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Bnode:
'''二叉树的节点'''
def __init__(self, root, left=None, right=None):
self.root = root
self.left = left
self.right = right

def getBTreewithBFS(l):
'''给定二叉树的层序遍历, 重建该二叉树'''
if l[0]:
root = Bnode(l[0])
nodes = [root]
id = 1
while nodes and id < len(l):
node = nodes[0] # 依次为每个节点分配子节点
node.left = Bnode(l[id]) if l[id] else None
nodes.append(node.left)
node.right = Bnode(l[id+1]) if id<len(l)-1 and l[id+1] else None
nodes.append(node.right)
id+=2 # 每次取出两个节点
nodes.pop(0)
return root
else:
return None

def PrintBTree(root):
'''打印二叉树, 从顶到底'''
tmp = []
result = []
if root == None:
return result
tmp.append(root)
while tmp:
newNode = tmp.pop(0)
if newNode == None:
result.append(None)
else:
result.append(newNode.root)
if newNode.left or newNode.right:
tmp.append(newNode.left)
tmp.append(newNode.right)
return result

#################################################################

def invertTree(root):
if root != None:
node = root
node.left, node.right = invertTree(node.right), invertTree(node.left)
else:
return None
return node

BT1 = Bnode(4, Bnode(2, Bnode(1), Bnode(3)), Bnode(7, Bnode(6), Bnode(9)))
BT2 = getBTreewithBFS([4,2,7,1,3,6,9])
print(PrintBTree(invertTree(BT1)))
print(PrintBTree(invertTree(BT2)))

4、leetcode104:二叉树的最大深度

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7]
返回它的最大深度 3

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Bnode:
'''二叉树的节点'''
def __init__(self, root, left=None, right=None):
self.root = root
self.left = left
self.right = right

def getBTreewithBFS(l):
'''给定二叉树的层序遍历, 重建该二叉树'''
if l[0]:
root = Bnode(l[0])
nodes = [root]
id = 1
while nodes and id < len(l):
node = nodes[0] # 依次为每个节点分配子节点
node.left = Bnode(l[id]) if l[id] else None
nodes.append(node.left)
node.right = Bnode(l[id+1]) if id<len(l)-1 and l[id+1] else None
nodes.append(node.right)
id+=2 # 每次取出两个节点
nodes.pop(0)
return root
else:
return None

def PrintBTree(root):
'''打印二叉树, 从顶到底'''
tmp = []
result = []
if root == None:
return result
tmp.append(root)
while tmp:
newNode = tmp.pop(0)
if newNode == None:
result.append(None)
else:
result.append(newNode.root)
if newNode.left or newNode.right:
tmp.append(newNode.left)
tmp.append(newNode.right)
return result

#################################################################

def maxDepth(root):
if root is None:
return 0
else:
left_height = maxDepth(root.left)
right_height = maxDepth(root.right)
return max(left_height, right_height) + 1

BT = getBTreewithBFS([3,9,20,None,None,15,7])
print(maxDepth(BT))

5、leetcode111:二叉树的最小深度

给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

示例:
给定二叉树 [3,9,20,null,null,15,7],
返回它的最小深度 2.

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Bnode:
'''二叉树的节点'''
def __init__(self, root, left=None, right=None):
self.root = root
self.left = left
self.right = right

def getBTreewithBFS(l):
'''给定二叉树的层序遍历, 重建该二叉树'''
if l[0]:
root = Bnode(l[0])
nodes = [root]
id = 1
while nodes and id < len(l):
node = nodes[0] # 依次为每个节点分配子节点
node.left = Bnode(l[id]) if l[id] else None
nodes.append(node.left)
node.right = Bnode(l[id+1]) if id<len(l)-1 and l[id+1] else None
nodes.append(node.right)
id+=2 # 每次取出两个节点
nodes.pop(0)
return root
else:
return None

def PrintBTree(root):
'''打印二叉树, 从顶到底'''
tmp = []
result = []
if root == None:
return result
tmp.append(root)
while tmp:
newNode = tmp.pop(0)
if newNode == None:
result.append(None)
else:
result.append(newNode.root)
if newNode.left or newNode.right:
tmp.append(newNode.left)
tmp.append(newNode.right)
return result

#################################################################

def minDepth(root):
if not root: return 0
if not root.left: return minDepth(root.right) + 1
if not root.right: return minDepth(root.left) + 1
return min(minDepth(root.left), minDepth(root.right)) + 1

BT = getBTreewithBFS([3,9,20,None,None,15,7])
print(minDepth(BT))

6、leetcode111:平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Bnode:
'''二叉树的节点'''
def __init__(self, root, left=None, right=None):
self.root = root
self.left = left
self.right = right

def getBTreewithBFS(l):
'''给定二叉树的层序遍历, 重建该二叉树'''
if l[0]:
root = Bnode(l[0])
nodes = [root]
id = 1
while nodes and id < len(l):
node = nodes[0] # 依次为每个节点分配子节点
node.left = Bnode(l[id]) if l[id] else None
nodes.append(node.left)
node.right = Bnode(l[id+1]) if id<len(l)-1 and l[id+1] else None
nodes.append(node.right)
id+=2 # 每次取出两个节点
nodes.pop(0)
return root
else:
return None

def PrintBTree(root):
'''打印二叉树, 从顶到底'''
tmp = []
result = []
if root == None:
return result
tmp.append(root)
while tmp:
newNode = tmp.pop(0)
if newNode == None:
result.append(None)
else:
result.append(newNode.root)
if newNode.left or newNode.right:
tmp.append(newNode.left)
tmp.append(newNode.right)
return result

#################################################################

def depth(root):
if not root:
return 0
return max(depth(root.left), depth(root.right)) + 1

def isBalanced(root):
if not root:
return True
if not isBalanced(root.left) or not isBalanced(root.right):
return False
depth_left, depth_right = depth(root.left), depth(root.right)
if abs(depth_left - depth_right) < 2:
return True
else:
return False

BT = getBTreewithBFS([3,9,20,None,None,15,7])
print(isBalanced(BT))

7、leetcode108:将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5]

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Bnode:
'''二叉树的节点'''
def __init__(self, root, left=None, right=None):
self.root = root
self.left = left
self.right = right

def getBTreewithBFS(l):
'''给定二叉树的层序遍历, 重建该二叉树'''
if l[0]:
root = Bnode(l[0])
nodes = [root]
id = 1
while nodes and id < len(l):
node = nodes[0] # 依次为每个节点分配子节点
node.left = Bnode(l[id]) if l[id] else None
nodes.append(node.left)
node.right = Bnode(l[id+1]) if id<len(l)-1 and l[id+1] else None
nodes.append(node.right)
id+=2 # 每次取出两个节点
nodes.pop(0)
return root
else:
return None

def PrintBTree(root):
'''打印二叉树, 从顶到底'''
tmp = []
result = []
if root == None:
return result
tmp.append(root)
while tmp:
newNode = tmp.pop(0)
if newNode == None:
result.append(None)
else:
result.append(newNode.root)
if newNode.left or newNode.right:
tmp.append(newNode.left)
tmp.append(newNode.right)
return result

#################################################################

def sortedArrayToBST(nums):
if not nums:
return
mid = len(nums)//2
root = Bnode(nums[mid])
root.left = sortedArrayToBST(nums[:mid])
root.right = sortedArrayToBST(nums[mid+1:])
return root

BT = sortedArrayToBST([-10,-3,0,5,9])
print(PrintBTree(BT))

8、leetcode617:合并二叉树

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Bnode:
'''二叉树的节点'''
def __init__(self, root, left=None, right=None):
self.root = root
self.left = left
self.right = right

def getBTreewithBFS(l):
'''给定二叉树的层序遍历, 重建该二叉树'''
if l[0]:
root = Bnode(l[0])
nodes = [root]
id = 1
while nodes and id < len(l):
node = nodes[0] # 依次为每个节点分配子节点
node.left = Bnode(l[id]) if l[id] else None
nodes.append(node.left)
node.right = Bnode(l[id+1]) if id<len(l)-1 and l[id+1] else None
nodes.append(node.right)
id+=2 # 每次取出两个节点
nodes.pop(0)
return root
else:
return None

def PrintBTree(root):
'''打印二叉树, 从顶到底'''
tmp = []
result = []
if root == None:
return result
tmp.append(root)
while tmp:
newNode = tmp.pop(0)
if newNode == None:
result.append(None)
else:
result.append(newNode.root)
if newNode.left or newNode.right:
tmp.append(newNode.left)
tmp.append(newNode.right)
return result

#################################################################

def mergeTrees(t1, t2):
if not t1 and t2:
return t2
elif t1 and t2:
t1.root = t2.root+t1.root
t1.left = mergeTrees(t1.left, t2.left)
t1.right = mergeTrees(t1.right, t2.right)
return t1

t1 = getBTreewithBFS([1,3,2,5])
t2 = getBTreewithBFS([2,1,3,None,4,None,7])
BT = mergeTrees(t1, t2)
print(PrintBTree(BT))
0%