从前序与中序遍历序列构造二叉树（Python实现）
一、了解三种树的遍历（前、中、后）
- 前序：根、左、右
- 中序：左、根、右
- 后序：左、右、根
前序遍历顾名思义就是根在最前面遍历，中序就是根在中间，后续就是根在后面。
# 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题解）
结合上图
递归思路
-
前序遍历的形式总是：[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
即根节点总是前序遍历中的第一个节点。
-
中序遍历的形式总是：[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。
这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。
三、代码实现
# 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