构造MaxTree

# -*- coding:utf-8 -*-

class MaxTree:
    def buildMaxTree(self,A, n):
        # write code here
        list1=[0]*n
        for i in range(n):
            max1=''
            max2=''
            if len(A[0:i])!=0:
                for j in A[i-1::-1]:
                    if j>A[i]:
                        max1=j
                        break
            if len(A[i+1:])!=0:
                for k in A[i+1:]:
                    if k>A[i]:
                        max2=k
                        break
            if max1=='' and max2!='':
                list1[i]=A.index(max2)
            elif max2=='' and max1!='':
                list1[i]=A.index(max1)
            elif max1=='' and max2=='':
                list1[i]=-1
            else:
                list1[i]=A.index(min(max1,max2))
        return list1

# -*- coding:utf-8 -*-
class MaxTree:
    def buildMaxTree(self, A, n):
        if n<1:
            return None
        if n==1:
            return [-1]
        num=[]
        for i in range(n):
            j=i
            find_left=False
            left=0
            while j>0 and not find_left:#找到左边的第一个比它大的数
                j-=1
                if A[j]>A[i]:
                    find_left=True
                    left=A[j]
            k=i
            find_right=False
            right=0
            while k<n-1 and not find_right:#找到右边的第一个比它大的数
                k+=1
                if A[k]>A[i]:
                    find_right=True
                    right=A[k]
            node_root=-1
            if find_left and find_right:#左右都能找到，则取较小数的下标
                node_root=A.index(min(left,right))
            elif find_right or find_left:#只在一边找到，则取该方向的下标
                node_root=A.index(max(left,right))
            else:#两边都没找到，则为根节点
                node_root=-1
            num.append(node_root)
        return num

# -*- coding:utf-8 -*-

class MaxTree:
    def buildMaxTree(self, A, n):
        # write code here
        if n<1:
            return None
        if n==1:
            return [-1]
        num=[]
        
        for i in range(n):
            j=i
            find_left=False
            left=0
            while j>0 and not find_left:
                j-=1
                if A[j]>A[i]:
                    find_left=True
                    left=A[j]
                
            k=i
            find_right=False
            right=0
            while k<n-1 and not find_right:
                k+=1
                if A[k]>A[i]:
                    find_right=True
                    right=A[k]

            node_root=-1
            if left>right and find_left and find_right:
                node_root=k
            elif left<right and find_left and find_right:
                node_root=j
            elif find_right and not find_left:
                node_root=k
            elif not find_right and find_left:
                node_root=j
            elif not find_right and not find_left:
                node_root=-1
            num.append(node_root)
        return num
                

    global findLeft

    global findRight

    def buildMaxTree( A, n):

        # write code here

        B = [ None ]*n

        for x in range( 0 ,n):

            left = findLeft(self,A,x)

            right = findRight(A,x,n)

            if left == None :

                if right == None :

                    B[x] = -1

                else :

                    B[x] = right

            else :

                if right == None :

                    B[x] = left

                else :

                    if A[left] > A[right]:

                        B[x] = right

                    else :

                        B[x] = left

        return B

    def findLeft(A,index):

        mid = A[index]

        if index<= 0 :

            return None

        else :

            while index -1 >= 0 :

                index = index - 1

                temp = A[index]

                if A[index]>mid:

                    return index

            if index == 0 :

                return None

    def findRight(A,index,n):

        mid = A[index]

        if index>=n -1 :

            return None

        else :

            while index +1 <n:

                index = index + 1

                if A[index]>mid:

                    return index

            if index == n -1 :

                return None

    if __name__ == '__main__' :

        A = [ 1477 , 563 , 345 , 425 , 1905 , 991 ]

        n = 4

        print buildMaxTree(A, 6 )