面试题07. 重建二叉树

题目描述

做题链接：面试题07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。

输入：

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

输出：

    3
   / \
  9  20
    /  \
   15   7

解题思路

• 解题思路:

  • 数据结构——二叉树

    根据 pre 确定 根节点

    根据 vin 确定左右子树的大小

  • 递归编程

• 注意点

  需要根据中序遍历结果，确定左子树长度 tin.index(value)

代码

class TreeNode:
     def __init__(self, x):
          self.val = x
          self.left = None
          self.right = None
        
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre) == 0 :
           return None
        if len(pre) == 1 :
           return TreeNode(pre[0])
        
        value = pre[0]
        root = TreeNode(value)
        # 截取左子树
        preLeft = pre[1:tin.index(value) + 1] # 先序遍历，从第二个开始截图 左子树长度的 数组
        tinLeft = tin[:tin.index(value)] # 中序遍历

        # 截取右子树
        preRight = pre[tin.index(value) + 1:] # 先序遍历， 左子树后的数组元素是 右子树
        tinRight = tin[tin.index(value) + 1:] # 中序遍历

        root.left = self.reConstructBinaryTree(preLeft, tinLeft)
        root.right = self.reConstructBinaryTree(preRight, tinRight)
        return root