重建二叉树

问题简述

给定二叉树的前序和中序遍历结果，重建二叉树；
规定二叉树中各节点的值都不相同；

重建二叉树_牛客题霸_牛客网

思路

• 前序遍历的第一个节点为根节点，在中序遍历中找到根节点的位置，其左边部分为左子树，右边为右子树，然后按前序遍历递归构建整个树；

Python

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pre int整型一维数组 
# @param vin int整型一维数组 
# @return TreeNode类
#
class Solution:
    def reConstructBinaryTree(self , pre: List[int], vin: List[int]) -> TreeNode:
        # write code here
        
        def dfs(p, i):
            if not p or not i: return None
            
            val = p[0]
            idx = i.index(val)
            node = TreeNode(val)
            
            node.left = dfs(p[1:idx + 1], i[:idx])
            node.right = dfs(p[idx + 1:], i[idx + 1:])
            
            return node
        
        return dfs(pre, vin)