Offer_day20_07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制：

0 <= 节点个数 <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码：

from leetcode_python.utils import *


class Solution:
    def __init__(self):
        pass

    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(preorder)==1: return TreeNode(preorder[0])
        for id,num in enumerate(inorder):
            if num==preorder[0]:
                head = TreeNode(num)
                head.left=self.buildTree(preorder[1:id+1],inorder[:id])
                head.right=self.buildTree(preorder[id+1:],inorder[id+1:])
                return head


    def buildTree_copy(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(preorder)==1: return TreeNode(preorder[0])
        preorder_ = [x for x in preorder]
        inorder_ = [x for x in inorder]
        for id,num in enumerate(inorder_):
            if num==preorder_[0]:
                head = TreeNode(num)
                # print(num,preorder,inorder)
                # print('left:',preorder[1:id+1],inorder[:id])
                # print('right:',preorder[id+1:],inorder[id+1:])
                head.left=self.buildTree(preorder_[1:id+1],inorder_[:id])
                head.right=self.buildTree(preorder_[id+1:],inorder_[id+1:])
                return head


def test(data_test):
    s = Solution()
    return s.buildTree(*data_test)


def test_obj(data_test):
    result = [None]
    obj = Solution(*data_test[1][0])
    for fun, data in zip(data_test[0][1::], data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result


if __name__ == '__main__':
    datas = [
        [[3,9,20,15,7],[9,3,15,20,7]],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{time.time() - t0}s')

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

备注：
GitHub：https://github.com/monijuan/leetcode_python

CSDN汇总：模拟卷Leetcode 题解汇总_卷子的博客-CSDN博客

可以加QQ群交流：1092754609

leetcode_python.utils详见汇总页说明
先刷的题，之后用脚本生成的blog，如果有错请留言，我看到了会修改的！谢谢！