BM31 对称的二叉树
url： 牛客
BM31
考察知识点： 二叉树、层次遍历
求解对称问题的常规思路就是从左边遍历一遍再从右边遍历一遍，然后如果对应位置相同就是对称的。
对于二叉树，很关键的一点的就是层次遍历的时候记得要把指向空值的节点也算进去，不然有可能发生位置不对的事。
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
|
class Solution:
def isSymmetrical(self , pRoot: TreeNode) -> bool:
if pRoot is None:
return True
left_queue, right_queue = [pRoot], [pRoot]
while len(left_stack) > 0 and len(right_stack) > 0:
left = left_queue.pop(0)
right = right_queue.pop(0)
if left is None and right is None:
continue
elif left is None or right is None or left.val != right.val:
return False
left_queue.append(left.left)
left_queue.append(left.right)
right_queue.append(right.right)
right_queue.append(right.left)
return 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
|
class Solution:
def compare_left_and_right(self, left_node: TreeNode, right_node: TreeNode):
if left_node is None and right_node is None:
return True
elif left_node is None or right_node is None or \
left_node.val != right_node.val:
return False
return self.compare_left_and_right(left_node.left, right_node.right) and \
self.compare_left_and_right(left_node.right, right_node.left)
def isSymmetrical(self , pRoot: TreeNode) -> bool:
if pRoot is None:
return True
return self.compare_left_and_right(pRoot.left, pRoot.right)
|
BM 32 合并二叉树
url： 牛客
BM32
考察知识点：二叉树、层次遍历
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
|
class Solution:
def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
if t1 is None or t2 is None:
return t1 if t1 is None else t2
t1_queue = [t1]
t2_queue = [t2]
while len(t1_queue) > 0 and len(t2_queue) > 0:
t1_node = t1_queue.pop(0)
t2_node = t2_queue.pop(0)
t1_node.val = t1_node.val + t2_node.val
if t1_node.left is None:
t1_node.left = t2_node.left
elif t2_node.left is not None:
t1_queue.append(t1_node.left)
t2_queue.append(t2_node.left)
if t1_node.right is None:
t1_node.right = t2_node.right
elif t2_node.right is not None:
t1_queue.append(t1_node.right)
t2_queue.append(t2_node.right)
return t1
|
BM 34 判断是不是二叉搜索树
url：牛客
BM34
考察知识点：二叉搜索树的定义
二叉搜索树定义：二叉搜索树是一种特殊的二叉树，它的每个节点值大于它的左子节点，且大于全部左子树的节点值，小于它右子节点，且小于全部右子树的节点值。因此二叉搜索树一定程度上算是一种排序结构。
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
|
class Solution:
def _isValidBST(self, root: TreeNode, pre_node: TreeNode, right_subtree: bool):
if root is None:
return True
if root.left is not None:
if right_subtree and pre_node is not None \
and root.left.val <= pre_node.val:
return False
if root.left.val >= root.val:
return False
if root.right is not None:
if not right_subtree and pre_node is not None \
and root.right.val >= pre_node.val:
return False
if root.right.val <= root.val:
return False
return self._isValidBST(root.left, root, False) and \
self._isValidBST(root.right, root, True)
def isValidBST(self , root: TreeNode) -> bool:
return self._isValidBST(root, None, False)
|
BM 35 判断是不是完全二叉树
url：牛客
BM35
考察知识点：二叉树层次遍历
完全二叉树的定义：若二叉树的深度为 h，除第 h
层外，其它各层的结点数都达到最大个数，第 h
层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含
[1~2h] 个节点）
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
|
class Solution:
def isCompleteTree(self , root: TreeNode) -> bool:
if root is None:
return True
last_layer = False
queue = [root]
next_layer = []
while len(queue) > 0:
node = queue.pop(0)
if node is None:
last_layer = True
else:
if last_layer:
return False
next_layer.append(node.left)
next_layer.append(node.right)
if len(queue) == 0 and len(next_layer) > 0:
if last_layer:
for item in next_layer:
if item is not None:
return False
queue = next_layer
next_layer = []
return True
|
上面这版写得比较啰嗦，用层次遍历解决会更好，但我感觉如果去掉完全二叉树"第
h
层所有的叶子结点都连续集中在最左边"的要求，那这版代码就会灵活起来。考虑这个特点的话，只需要使用层次遍历，在None之后继续出现非None的节点判定为非完全二叉树。实现如下：
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
|
class Solution:
def isCompleteTree(self , root: TreeNode) -> bool:
if root is None:
return True
appear_None = False
queue = [root]
while len(queue) > 0:
node = queue.pop(0)
if node is not None and appear_None:
return False
elif node is None:
appear_None = True
else:
queue.append(node.left)
queue.append(node.right)
return True
|
上面几题看下来，发现二叉树类的问题有几个特点： 1.
如果涉及到二叉树的搜索问题，那么递归的实现往往会比较清晰。 2.
如果涉及到二叉树的形态、结构之类的问题，考虑层次遍历会事半功倍。
