子寒的博客
0%

leetcode105 Construct Binary Tree from Preorder and Inorder Traversal 解题报告

发表于 分类于

英文原题

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 105

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

分析

    题目给出了一个二叉树的先序遍历和中序遍历需要我们还原这个二叉树。首先通过先序遍历我们可以知道根节点就是先序遍历的第一个数，又因为题目中说给到的数都是唯一的，所以我们可以把这个根节点的值放到中序遍历的序列里面，这个值的左边就是左子树的中序，右边就是右子树的中序，然后记录左子树的节点个数，再去先序遍历里面根节点后面提取相应的个数就是左子树的先序，剩下的就是右子树的先序。

python 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:
            return
        rootval = preorder[0]
        root = TreeNode(rootval)
        leftInorder = inorder[:inorder.index(rootval)]
        rightInorder = inorder[inorder.index(rootval)+1:]
        leftPreorder = preorder[1:len(leftInorder)+1]
        rightPreorder = preorder[len(leftInorder)+1:]
        root.left = self.buildTree(leftPreorder, leftInorder)
        root.right = self.buildTree(rightPreorder, rightInorder)
        
        return root

今天刚做了核酸检测。。