剑指 中序前序构建二叉树

注意 pre 为空的条件判断。重建二叉树最开始需要通过TreeNode 构建一个根节点，将root,root.left,root.right进行构建。同时仍需要判断输入数组的index是否超出范围,也就是 左子树的长度是否为0(左子树为空)，是否为len-1(右子树为空)
o(n^2) 将查找index 换为hashmap 会变成o(n)

class Solution:
    def reConstructBinaryTree(self, pre, tin):


        if len(pre)==0:
            return None
        root=TreeNode(pre[0])

        root_index=tin.index(pre[0])
        left_length=len(tin[:root_index])
        if left_length==0:
            root.left=None
        else:

            root.left=self.reConstructBinaryTree(pre[1:left_length+1], tin[:root_index])

        if left_length==len(pre)-1:
            root.right=None
        else:
            root.right=self.reConstructBinaryTree(pre[left_length+1:], tin[root_index+1:])       

        return root


###改成hashmap

class Solution:
    def reConstructBinaryTree(self, pre, tin):


       def rebuild(preo,tino,pre_left,pre_right,tin_left,tin_right):
            if pre_left>pre_right:
                return None
            root_index=rootindex[preo[pre_left]]

            root=TreeNode(preo[pre_left])


            left_length=len(tino[tin_left:root_index])
            print(left_length)
            root.left=rebuild(preo,tino,pre_left+1,pre_left+left_length,tin_left,root_index-1)

            root.right=rebuild(preo,tino,pre_left+left_length+1,pre_right,root_index+1,tin_right)

            return root

       rootindex={item: i for i,item in enumerate(tin)} 
       n=len(pre)
       return rebuild(pre,tin,0, n-1, 0, n-1)

另一种递归 需要注意的是 如果不动态传递tin pre 求左子树长度一定要带上左边界。

class Solution:
    def reConstructBinaryTree(self, pre, tin): 


       def rebuild(preo,tino,pre_left,pre_right,tin_left,tin_right):
            if pre_left>pre_right:
                return None
            root_index=tin.index(preo[pre_left])

            root=TreeNode(preo[pre_left])


            left_length=len(tino[tin_left:root_index])
            print(left_length)
            root.left=rebuild(preo,tino,pre_left+1,pre_left+left_length,tin_left,root_index-1)

            root.right=rebuild(preo,tino,pre_left+left_length+1,pre_right,root_index+1,tin_right)

            return root


       n=len(pre)
       return rebuild(pre,tin,0, n-1, 0, n-1)

递归简洁版，注意pop()中不填默认-1即最后一个元素，所以需要填0，即除去下标为0元素同时给返回该元素，每次递归不将pre数组细化，pre的作用就是找到第一个元素即为根，每次改变tin数组，所以判断条件需要判断tin是否为空了。

class Solution:
    def reConstructBinaryTree(self, pre, tin):


        if len(tin)==0:
            return None

        root=TreeNode(pre.pop(0))

        root_index=tin.index(root.val)

        #left_length=len(tin[:root_index])


        root.left=self.reConstructBinaryTree(pre, tin[:root_index])


        root.right=self.reConstructBinaryTree(pre, tin[root_index+1:])       

        return root

迭代

因为前序遍历一直从根到最左的节点，然后是右节点，而中序是从最左开始遍历，所以可以通过前序当前元素是否与中序最开始元素相同，判断是否当前元素为最左，当到了最左节点，就要开始考虑右节点的位置，右节点的位置通过判断从栈弹出的前序左子树是否和中序的元素相同（一正一反）当出现不相同时候，右节点应为他的前一个弹出的栈顶元素的右子树。

所以先从第一个元素往后（第一个元素已经入栈）开始找左节点（判断栈顶元素是否与中序遍历第一个元素相等即判断栈顶元素是否是最左节点），如果不是就赋给左子树然后入栈
如果是，就证明下一个节点将是右子树，那么就要找他是谁的右子树，通过栈顶元素与中序遍历中元素比较，找到不同的那个点，前一个栈顶的元素就是他的根。

直到 index 对应的元素不等于栈顶节点。按照这样的过程，我们弹出的最后一个节点 x 就是 10 的双亲节点，这是因为 10 出现在了 x 与 x 在栈中的下一个节点的中序遍历之间，因此 10 就是 x 的右儿子。

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(preorder)==0:
            return None

        stack=[]
        root=TreeNode(preorder[0])
        stack.append(root)
        index=0
        for i in range(1,len(preorder)):
            if stack[-1].val!=inorder[index]:
                node=stack[-1]
                node.left=TreeNode(preorder[i])
                stack.append(node.left)
            else:
                while stack and stack[-1].val==inorder[index]:
                    index+=1
                    node=stack.pop()

                node.right=TreeNode(preorder[i])
                stack.append(node.right)


        return root