从前序与中序遍历序列构造二叉树（Python实现）

一、了解三种树的遍历（前、中、后）

1. 前序：根、左、右
2. 中序：左、根、右
3. 后序：左、右、根

前序遍历顾名思义就是根在最前面遍历，中序就是根在中间，后续就是根在后面。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        list1 = []
        def preorder(root):
            """
            preorder就是前序遍历的算法实现（可以把这个算法当作规律）
            1.如果节点不为空，继续前序遍历
            2.输出当前节点（当作根）
            3.如果当前节点的左字树不为空，则继续前序遍历
            4.如果当前节点的右子树不为空，则继续前序遍历
            这里要注意左子树的递归，他没递归完，是不会执行右子树的递归的
            """
            if root is None: return
            list1.append(root.val)
            preorder(root.left)
            preorder(root.right)
        preorder(root)
        return list1

接下来做个题来检验一下吧

二、了解前序和中序遍历的序列规律（参照Leetcode第105题解）

结合上图

递归思路

1. 前序遍历的形式总是：[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

   即根节点总是前序遍历中的第一个节点。

2. 中序遍历的形式总是：[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。

这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

三、代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(preorder) > 0:
            root = TreeNode(preorder[0])
            index = inorder.index(preorder[0])
            root.left = self.buildTree(preorder[1:index+1], inorder[:index])
            root.right = self.buildTree(preorder[index+1:], inorder[index+1:])
            return root

参考文章