题目

根据一棵树的前序遍历与中序遍历构造二叉树。
image.png

思路

由前序遍历， 可以知道根节点；根据根节点，可以把中序遍历分为左、右两颗子树。

  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.         node_index= {val : index for index, val in enumerate(inorder)}
  11.         def helper(left, right):
  12.             if left > right: return
  13.             val = preorder.pop(0)
  14.             index = node_index[val]
  15.             root = TreeNode(val)
  17.             root.left = helper(left, index - 1)
  18.             root.right = helper(index + 1, right)
  20.             return root
  22.         return  helper(0, len(inorder) - 1)