106 letcode - 重建二叉树

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)