感觉写了一个世纪，终于把二叉树的章节过完了。还是挺充实开心的，以前确实没这么亲密地接触过二叉树。 ## BM 39 序列化二叉树

url：BM 39

考察知识点：二叉树的遍历，序列化及反序列化

序列化及反序列化的定义：

序列化：把对象转化为可传输的字节序列过程称为序列化。

反序列化：把字节序列还原为对象的过程称为反序列化。

用层次遍历序列化和反序列化二叉树，实现如下：

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
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        # 使用层次遍历来序列化
        if root is None:
            return ""

        queue = [root]
        result = []
        while len(queue) > 0:
            node = queue.pop(0)
            if node is None:
                result.append("#")
            else:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
        return ", ".join(result)
            

    def Deserialize(self, s: str):
        # write code here
        if len(s) == 0:
            return None
        item_list = s.split(", ")
        
        # 按部就班初始化所有节点
        head = TreeNode(int(item_list[0]))
        last_layer = [head]
        this_layer = []

        for i in range(1, len(item_list)):
            parent_node = last_layer[0]
            current_node = TreeNode(int(item_list[i])) if item_list[i] != "#" else None

            if i % 2 == 1:
                parent_node.left = current_node
            else:
                parent_node.right = current_node
            if current_node is not None:
                this_layer.append(current_node)
            if i % 2 == 0:
                last_layer.pop(0)
                if len(last_layer) == 0:
                    last_layer = this_layer
                    this_layer = []
        return head

用前序遍历完成二叉树的序列化和反序列化：

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
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        # 使用前序遍历来序列化
        if root is None:
            return ""

        stack = [root]
        result = []
        while len(stack) > 0:
            node = stack.pop()

            if node is None:
                result.append("#")
                continue
            
            result.append(str(node.val))

            stack.append(node.right)
            stack.append(node.left)
        return ", ".join(result)

    def deserialize(self, root: TreeNode, item_list: List[str]):
        # 取出左节点
        node_val = item_list.pop(0)
        if node_val == "#":
            root.left = None
        else:
            node = TreeNode(int(node_val))
            root.left = node
            # 有左节点的话得看子节点的左右节点了
            self.deserialize(node, item_list)
        
        # 取出右节点
        node_val = item_list.pop(0)
        if node_val == "#":
            root.right = None
        else:
            node = TreeNode(int(node_val))
            root.right = node
            # 有右节点的话得看子节点的左右节点了
            self.deserialize(node, item_list)



    def Deserialize(self, s: str):
        # write code here
        if len(s) == 0:
            return None
        item_list = s.split(", ")
        
        # 按部就班初始化所有节点
        head = TreeNode(int(item_list.pop(0)))
        if len(item_list) > 0:
            self.deserialize(head, item_list)
        return head

BM 40 重建二叉树

url：牛客 BM40

考察知识点：二叉树前序和中序遍历

这道题的一个核心就是要知道如果得知某个树的根节点，那么通过查找中序遍历中根节点的位置，可以知道该树左子树的所有节点和右子树的所有节点。比如中序遍历是[3,2,4,1,6,5,7]，如果知道根节点是1，那么左子树有节点[3,2,4]，右子树有节点[6,5,7]。当左子树拥有的节点为空时，那么根节点不存在左子树。

前序遍历就可以为我们提供根节点的信息，承接上个例子，前序遍历如果为[1,2,3,4,5,6,7]，那么第一个根节点肯定是1。用1分割好中序遍历，可以得到左子树节点为[3,2,4]，右子树有节点[6,5,7]。那对前序遍历进行过滤，可以知道左子树的前序遍历为[2,3,4]，右子树的前序遍历为[5,6,7]。再看左子树的前序遍历知道左子树的根节点为2，再重复分割一下左子树的左子树的节点为[3]，左子树的右子树节点为[4]，这样就可以知道左子树的构型为：

如上图所示，如果我们以同样的方式递归把右子树的情况也获取出来，就可以重建得到最终的树了。

以上逻辑的Python代码实现如下：

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 TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param preOrder int整型一维数组 
# @param vinOrder int整型一维数组 
# @return TreeNode类
#
class Solution:
    def filter_list(self, root: TreeNode, preOrder: List[int], vinOrder: List[int]):
        root_val = root.val

        for i in range(len(vinOrder)):
            if vinOrder[i] == root_val:
                break
        
        left_vinOrder = vinOrder[:i]
        right_vinOrder = vinOrder[i+1:]


        left_preOrder = [v for v in preOrder if v in left_vinOrder]
        right_preOrder = [v for v in preOrder if v in right_vinOrder]

        return left_preOrder, left_vinOrder, right_preOrder, right_vinOrder


    def reConstruct(self, root: TreeNode, left_preOrder: List[int], left_vinOrder: List[int], right_preOrder: List[int], right_vinOrder: List[int]):
        if len(left_preOrder) == 0:
            root.left = None
        else:
            node_val = left_preOrder.pop(0)
            root.left = TreeNode(int(node_val))
            # 递归构建左子树
            self.reConstruct(root.left, *self.filter_list(root.left, left_preOrder, left_vinOrder))
        
        if len(right_preOrder) == 0:
            root.right = None
        else:
            node_val = right_preOrder.pop(0)
            root.right = TreeNode(int(node_val))
            # 递归构建右子树
            self.reConstruct(root.right, *self.filter_list(root.right, right_preOrder, right_vinOrder))


    def reConstructBinaryTree(self , preOrder: List[int], vinOrder: List[int]) -> TreeNode:
        # write code here
        if len(preOrder) == 0:
            return None
        
        root = TreeNode(preOrder.pop(0))
        self.reConstruct(root, *self.filter_list(root, preOrder, vinOrder))
        return root

进一步追问：有了先序遍历和中序遍历就能唯一确定一棵二叉树树吗？

这个我觉得是要分情况的，这个题目能做到这点很大程度上仰仗“pre 和 vin 均无重复元素”这个条件。假设一下，如果先序遍历和中序遍历都是[1,1,1]的话，那这棵树似乎有3种合规的重建方式，不能唯一确定某一棵二叉树。如果加上没有重复元素这点，那就可以唯一确定。

那在没有重复元素的情况下，哪两种遍历能唯一确定一棵二叉树呢？

首先前序和中序是可以的，原因上面讨论过了。后序和中序也是可以的，只不过后序遍历从后面取根节点的值。不可以唯一确定的是前序遍历和后序遍历，可以举一个反例来说明。

这两个case里，前序和后序遍历都是[1,2]和[2,1]，但一个2在左子树上一个2在右子树上。因此前序和后序遍历是不能唯一确定一棵二叉树的。

那加上层序遍历呢？我的理解是如果这棵树是完全二叉树（若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边的二叉树），只用层序遍历就可以唯一确定这棵树了。否则，则必须要结合中序遍历才能确定（这句话可能也存在漏洞，我没找到不能这样做的反例）。将上面那个两个case做一个表格：

遍历方式 case 1 case 2
层次遍历 1，2 1，2
前序遍历 1，2 1，2
中序遍历 2，1 1，2
后序遍历 2，1 2，1

可以发现层次遍历、前序遍历和后序遍历对这两个不同的case都产生同样的结果，因此这3个遍历方式任意组合即使在节点值不重复的条件下也不能重建唯一的二叉树。

BM 41 输出二叉树的右视图

url：牛客 BM41

考察知识点：二叉树重建，二叉树层次遍历

把之前的BM40那个二叉树重新写了一下，重建二叉树然后分层层次遍历就可以了，实现如下：

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
64
65
66
67
68
69
70
71
72
73
74
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求二叉树的右视图
# @param preOrder int整型一维数组 先序遍历
# @param inOrder int整型一维数组 中序遍历
# @return int整型一维数组
#
class Solution:
    def reConstruct(self, root: TreeNode, preOrder: List[int], inOrder: List[int]):
        # 最后返回头节点
        # 处理分割
        for i in range(len(inOrder)):
            if inOrder[i] == root.val:
                break
        
        left_inOrder = inOrder[:i]
        left_preOrder = preOrder[:i]

        right_inOrder = inOrder[i+1:]
        right_preOrder = preOrder[i:]

        # 重建左子树
        if len(left_inOrder) == 0:
            root.left = None
        else:
            val = left_preOrder.pop(0)
            left_node = TreeNode(int(val))
            root.left = self.reConstruct(left_node, left_preOrder, left_inOrder)
        
        # 重建右子树
        if len(right_inOrder) == 0:
            root.right = None
        else:
            val = right_preOrder.pop(0)
            right_node = TreeNode(int(val))
            root.right = self.reConstruct(right_node, right_preOrder, right_inOrder)

        return root

    def solve(self , preOrder: List[int], inOrder: List[int]) -> List[int]:
        # write code here
        if len(preOrder) == 0:
            return []

        root_val = preOrder.pop(0)
        root = TreeNode(int(root_val))

        # 重建二叉树
        root = self.reConstruct(root, preOrder, inOrder)

        # 分层层次遍历
        current_layer = [root]
        next_layer = []
        result = [root.val]

        while len(current_layer) > 0:
            node = current_layer.pop(0)

            if node.left is not None:
                next_layer.append(node.left)
            
            if node.right is not None:
                next_layer.append(node.right)

            # 判断当前层是否被访问完
            if len(current_layer) == 0 and len(next_layer) > 0:
                # 更新右视图
                result.append(next_layer[-1].val)
                # 更新当前层和下一层
                current_layer = next_layer
                next_layer = []

        return result