剑指Offer07.重建二叉树

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

例如,给出:

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

限制:

0 <= 节点个数 <= 5000

通过前序遍历确定根节点,再通过中序遍历确定左右子树,递归上述过程即可得出树的结构。

比如,当递归到最后一层时,如何确定最树结构?

preorder = [20, 15, 7]
inorder = [15, 20, 7]
  1. 根据 preorder 获得根节点: root = preorder[0]
  2. 在 inorder 中找到 root 的位置:index = 1
  3. 利用 index ,在 inorder 中确定左子树和右子树数量:left_number = 1, right_number = 1 以及子树的 inorder 。
  4. 利用子树数量,从 preorder 中确定子树的 preorder 。

image

得到左右子树的 preordr 和 inorder 后,继续上述步骤,以左子树为例:

preorder = [15]
inorder = [15]
  1. 根据 preorder 获得根节点:root = preorder[0] = 15
  2. 在 inorder 中找到 root 的位置:index = 0
  3. 利用 index ,在 inorder 中确定左子树和右子树数量:left_number = 0, right_number = 0 以及子树的 inorder
  4. 利用子树数量,从 preorder 中确定子树的 preorder 。

image

  1. 发现 preorder 为空,返回 None
  2. 到此确定左子树是 15 。
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:
            return None

        index = self.find_index(preorder, inorder)
        root = TreeNode(preorder[0])
        root.left = self.buildTree(preorder[1: index + 1], inorder[0: index])
        root.right = self.buildTree(preorder[index + 1: ], inorder[index + 1:])

        # 1. 当子树的 preorder 或者 inorder 为空时,第一个子树构建完毕
        # 2. 当第一个子树构建完毕时,第二个子树构建完毕...
        return root
    
    def find_index(self, preorder, inorder):
        """
        寻找中序遍历中根节点的位置
        """
        for index, value in enumerate(inorder):
            if value == preorder[0]:
                return index