题解 | #重建二叉树#

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param preOrder int整型一维数组 
# @param vinOrder int整型一维数组 
# @return TreeNode类
#递归思路，本质感觉就是找规律，前序遍历的结果可以确定根节点，中序遍历的结果能确认左右子树
class Solution:
    def reConstructBinaryTree(self , preOrder: List[int], vinOrder: List[int]) -> TreeNode:
        n = len(preOrder)
        m = len(vinOrder)
        #容错处理，如果为0，则返回none
        if n ==0 or m == 0:
            return None
        #利用前序遍历结果构建好根节点
        root= TreeNode(preOrder[0])
        for i in range(len(vinOrder)):
            #找到中序遍历中的根节点位置
            if preOrder[0] == vinOrder[i]:
                #左子树的前序遍历list
                leftpre = preOrder[1:i+1]
                #左子树的中序遍历list
                leftvin = vinOrder[:i]
                #递归调用依次拿到根值放到左侧
                root.left = self.reConstructBinaryTree(leftpre,leftvin)
                #右侧也是同样的逻辑
                rightpre = preOrder[i+1:]
                righrvin = vinOrder[i+1:]
                root.right = self.reConstructBinaryTree(rightpre,righrvin)
                break
        return root






        # write code here

这题感觉确实有点找规律那意思了，重建二叉树的思路大概是

首先要找到根节点（前序遍历结果的首个元素）

其次基于根节点区分开左右子树，分别在左右子树里找到子节点构建树

如何区分？在中序遍历中找到根节点，节点的两侧分别就是左右子树的中序遍历，前序遍历也满足条件能找出来

接下来就是构建的问题，这个时候就涉及到规律了，我们可以发现

区分开左右子树的前序遍历和中序遍历结果后，发现子树也可以满足递归条件，即子树也可以先找根，再以根进一步区分左右子树，此时的根就是重建二叉树的左右子节点，所以直接递归调用即可