重建二叉树 -- 结合前中后序列

相关题目：
105. 从前序与中序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树
889. 根据前序和后序遍历构造二叉树

class BuildTree:
    def __init__(self):
        self.in_val2idx = dict()
        self.post_val2idx = dict()

    def buildTree_pre_in(self, preorder: [], inorder: []) -> TreeNode:
        """
        https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
        通过前序和中序遍历序列 构造二叉树，返回root节点
        :param preorder: 前序遍历
        :param inorder: 中序遍历
        :return:
        """
        for idx, val in enumerate(inorder):
            self.in_val2idx[val] = idx

        return self.build_pre_in(preorder, 0, len(preorder) - 1,
                                 inorder, 0, len(inorder) - 1)

    def build_pre_in(self, preorder, preStart, preEnd, inorder, inStart, inEnd):
        if preStart > preEnd:
            return None

        rootVal = preorder[preStart]
        idx = self.in_val2idx[rootVal]

        rootNode = TreeNode(rootVal)
        leftSize = idx - inStart
        rootNode.left = self.build_pre_in(preorder, preStart + 1, preStart + leftSize,
                                          inorder, inStart, idx - 1)
        rootNode.right = self.build_pre_in(preorder, preStart + leftSize + 1, preEnd,
                                           inorder, idx + 1, inEnd)

        return rootNode

    def buildTree_post_in(self, postorder: [], inorder: []) -> TreeNode:
        """
        https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
        通过后序和中序遍历序列 构造二叉树，返回root节点
        :param postorder: 后序遍历
        :param inorder: 中序遍历
        :return:
        """
        for idx, val in enumerate(inorder):
            self.in_val2idx[val] = idx

        return self.build_post_in(postorder, 0, len(postorder) - 1,
                                  inorder, 0, len(inorder) - 1)

    def build_post_in(self, postorder, postStart, postEnd, inorder, inStart, inEnd):
        if postStart > postEnd:
            return None

        rootVal = postorder[postEnd]
        idx = self.in_val2idx[rootVal]
        leftSize = idx - inStart

        rootNode = TreeNode(rootVal)
        rootNode.left = self.build_post_in(postorder, postStart, postStart + leftSize - 1,
                                           inorder, inStart, idx - 1)
        rootNode.right = self.build_post_in(postorder, postStart + leftSize, postEnd - 1,
                                            inorder, idx + 1, inEnd)

        return rootNode

    def buildTree_pre_post(self, preorder: [], postorder: []) -> TreeNode:
        """
        https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/description/
        这两种组合无法确定唯一的原始二叉树，返回任意一种即可
        通过前序和后序遍历 构造二叉树
        :param preorder: 前序遍历
        :param postorder: 后序遍历
        :return:
        """
        for idx, val in enumerate(postorder):
            self.post_val2idx[val] = idx

        return self.build_pre_post(preorder, 0, len(preorder) - 1,
                                   postorder, 0, len(postorder) - 1)

    def build_pre_post(self, preorder, preStart, preEnd, postorder, postStart, postEnd):
        if preStart > preEnd:
            return None

        if preStart == preEnd:
            return TreeNode(preorder[preStart])

        rootVal = preorder[preStart]
        idx = self.post_val2idx[preorder[preStart + 1]]
        leftSize = idx - postStart + 1

        rootNode = TreeNode(rootVal)
        rootNode.left = self.build_pre_post(preorder, preStart + 1, preStart + leftSize,
                                            postorder, postStart, idx)
        rootNode.right = self.build_pre_post(preorder, preStart + leftSize + 1, preEnd,
                                             postorder, idx + 1, postEnd - 1)

        return rootNode


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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101