class Solution:
"""
内存条里，有两个区域，堆和栈
其中，栈是我们函数跳转的关键，顺序是先进后出；
通过压栈出栈，可以实现递归。
《1》当到达递归终止条件时候，则开始返回。
例如： 先序遍历二叉树中，每个节点都要执行三个操作
根 左 右
当对左子树进行遍历的时候呢，可能这个左子树里还有很多子树，所有会在左子树里进行压栈，当某个
节点没有左右子节点时候出栈。
1.1 1
2 3
4 5 6 7
遍历该数，顺序为根 左 右
>>1
对 2 4 5 ,则
>>2,4
4 的左子树为空则，返回上一层，执行完根 左，继续执行5，则 2 4 ->5
>>5
5 的左右子树为空，则返回上层2 ，以2为根节点的树遍历完成，再向上返回一层递归，返回到以1为
根节点的树
接下来则遍历以1为根节点的右子树 3 6 7
......
......
"""
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
index = {val:i for i,val in enumerate(inorder)}
print(index)
# build（当前树的列表-先序遍历中根节点的位置，
# 当前树的列表-中序遍历中左边界，
# 当前树的列表-中序遍历中右边界）
def build (root,left,right):
# 【1】退出条件
# 退出条件， 根 左 右，是二叉树基本规律,关于二叉树几乎都是这么做的
if left>right:return
rootval= preorder[root]
print(rootval)
idroot=index[rootval]
print(idroot)
rootnode=TreeNode(preorder[root])
# print(rootnode.val)
leftsize = idroot - left
# 【2】 左右
rootnode.left = build(root+1,left,idroot-1)
rootnode.right = build(root+leftsize+1,idroot+1,right)
return rootnode
return build(0,0,len(inorder)-1)
