重建二叉树

"""
#算法应用在实例的过程，防止看不懂：
#前序序列：1 2 3 4 5 6 7
#中序序列：3 2 4 1 6 5 7
#此算法过程： 
#pre : 1 2 3 4 5 6 7
#tin : 3 2 4 1 6 5 7
#-》输入的pre[0]是当前node的元素，赋值tree.val = 1比如
#-》 检查tin中哪个元素与pre第一个相同（即1）
#发现tin中位置3的1为中心节点
#-》 先判断是否可分，如果可分，tin分成左右部，3 2 4 和 6 5 7
#-》 从左至右检查pre中哪个元素与左边tin中某个元素相同
#-》记录tin中相同元素的位置，比如对3 2 4 来说， pre中2为第一个与左边tin中某元素相同的数
#-》则左边递归调用输入pre[k::],k即2在pre中位置
#-》即左边递归输入 pre' 为 2 3 4 5 6 7 ，左边tin为324
#-》右边tin同理，递归。。。。输入pre' 为5 6 7 ，右边tin为6 5 7

.......以此无限类推

class TreeNode:
    def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:
    def reConstructBinaryTree(self, pre , tin) :
        # set node value
        tree = TreeNode (pre[0]) ;
        
        # check whether tin is splitable(at least one element)
        if len(tin) > 1 :
            
            # by firstly check the possible root node of current tree/subtree in pre list
            flag = 0 ;
            for j in range( len(pre) ):
                for k in range( len(tin) ):
                    if pre[j] == tin[k] :
                        # know the postiion of root node in tin
                        rootposintin = k ;  
                        # then flag
                        flag = 1 ;
                # if already find match
                # break loop
                if flag == 1 :
                    break ;
            
            
            
            # split two parts according to root node
            # must ensure two parts are splitable 
            # recursive left part
            if rootposintin > 0:
                lefttin = tin[0:rootposintin] ;
                
                # now decide which part of pre list will be entered into recursive method
                # we need to find the next element in pre list which is also included in tin list
                flag = 0 ;
                for j in range( len(pre) ):
                    for k in range( len(lefttin)) :
                        if pre[j] == lefttin[k] :
                            # then flag
                            flag = 1 ;
                    # if already find match
                    # break loop
                    if flag == 1 :
                        break ;    
                
                # now obtain part of pre list for left recursive method
                preforleft = pre[j::] ;
                
                # recursive left part
                tree.left = self.reConstructBinaryTree( preforleft , lefttin ) ;
                
                
            # recursive right part    
            if rootposintin + 1 < len(tin):
                righttin = tin[rootposintin+1::] ;
            
                # now decide which part of pre list will be entered into recursive method
                # we need to find the next element in pre list which is also included in tin list
                flag = 0 ;
                for j in range( len(pre) ):
                    for k in range( len(righttin)) :
                        if pre[j] == righttin[k] :
                            # then flag
                            flag = 1 ;
                    # if already find match
                    # break loop
                    if flag == 1 :
                        break ;    
                
                # now obtain part of pre list for right recursive method
                preforright = pre[j::] ;
                
                # recursive right part
                tree.right = self.reConstructBinaryTree( preforright , righttin ) ;
                         
        return tree ;