题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
image.png

思路

知道前序遍历，那么第一个数就是根节点。该根节点的左节点、右节点怎么找？
看中序，以根节点为分割，左边9是左节点，右边[15, 20, 7]是右节点。
再看前序，找出根节点。
……
递归

代码

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution:
  9.     def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
  10.         if not inorder:
  11.             return None
  13.         root = TreeNode(preorder.pop(0))
  14.         #利用python数组的index函数来定位根节点在inorder数组中的位置。
  15.         index = inorder.index(root.val) 
  16.         # preorder数组不需要进行切片操作，递归终止条件主要靠代码前两行中的not inorder来终止。
  17.         root.left = self.buildTree(preorder, inorder[:index])
  18.         root.right = self.buildTree(preorder, inorder[index + 1:])
  19.         return root

List : index() 函数用于从列表中找出某个值第一个匹配项的索引位置。