1. 有一棵二叉树，请设计一个算法，按照层次打印这棵二叉树。

给定二叉树的根结点root，请返回打印结果，结果按照每一层一个数组进行储存，所有数组的顺序按照层数从上往下，且每一层的数组内元素按照从左往右排列。保证结点数小于等于500。

# -*- coding:utf-8 -*-
 
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class TreePrinter:
    def printTree(self, root):
        # write code here
        result = []
        temp = []
        queue = []
        last = nlast = root
        queue.append(root)
        while queue:
            cur = queue.pop(0)
            temp.append(cur.val)
            if cur.left:
                queue.append(cur.left)
                nlast = cur.left
            if cur.right:
                queue.append(cur.right)
                nlast = cur.right
            if cur == last:
                result.append(temp[:])
                temp = []
                last = nlast
        return result

2. 对于一个int数组，请编写一个归并排序算法，对数组元素排序。

给定一个int数组A及数组的大小n，请返回排序后的数组。

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

class MergeSort:
    def mergeSort(self, A, n):
        # write code here
        if len(A)<=1:
            return A
        num = len(A)/2
        left = self.mergeSort(A[:num],num)
        right = self.mergeSort(A[num:],num)
        
        i,j = 0,0
        result = []
        while i<len(left) and j<len(right):
            if left[i]<=right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result += left[i:]
        result += right[j:]
        return result
        

3. 对于一个int数组，请编写一个快速排序算法，对数组元素排序。

给定一个int数组A及数组的大小n，请返回排序后的数组。

# -*- coding:utf-8 -*-
class QuickSort:
    def quickSort(self, A, n):
        # write code here
        if len(A) <= 1:
            return A 
        key = A[0]
        left = []
        right = []
        for i in range(1,len(A)):
            if A[i] <= key:
                left.append(A[i])
            else:
                right.append(A[i])
        result = self.quickSort(left,len(left)) + [key] + self.quickSort(right,len(right))
        return result

4. 对于一个int数组，请编写一个堆排序算法，对数组元素排序。

给定一个int数组A及数组的大小n，请返回排序后的数组。

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

class HeapSort:
    def heapSort(self, A, n):
        if A is not None and n >= 2:
            self.buildMaxHeap(A, n)
            for i in range(n - 1, 0, -1):
                A[0], A[i] = A[i], A[0]
                self.maxHeapify(A, i, 0)
        return A
    def buildMaxHeap(self, arr, heap_size):
        if heap_size < 2:
            return
        for i in range(heap_size/2-1, -1, -1):
            self.maxHeapify(arr, heap_size, i)
    def maxHeapify(self, arr, heap_size, root_pos):
        left_child = 2 * root_pos + 1
        right_child = left_child + 1
        max_value_pos = root_pos
        if left_child < heap_size and arr[left_child] > arr[max_value_pos]:
            max_value_pos = left_child
        if right_child < heap_size and arr[right_child] > arr[max_value_pos]:
            max_value_pos = right_child
        if max_value_pos != root_pos:
            arr[root_pos], arr[max_value_pos] = arr[max_value_pos], arr[root_pos]
            self.maxHeapify(arr, heap_size, max_value_pos)

找到第K大值

def buildMaxHeap(A,n):
    for i in range(n/2-1,-1,-1):
        maxHeapify(A,n,i)

def maxHeapify(A,n,root_pos):
    max_val_pos = root_pos
    left_pos = 2*root_pos + 1
    right_pos = left_pos + 1
    if left_pos<n and A[left_pos] > A[max_val_pos]:
        max_val_pos = left_pos
    if right_pos<n and A[right_pos] > A[max_val_pos]:
        max_val_pos = right_pos
    if max_val_pos != root_pos:
        A[max_val_pos], A[root_pos] = A[root_pos], A[max_val_pos]
        maxHeapify(A,n,max_val_pos)

def heapSort(A,n,K):
    if n<2:
        return A
    buildMaxHeap(A,n)
    for i in range(n-1,n-1-K,-1):
        A[i], A[0] = A[0],A[i]
        maxHeapify(A,i,0)
    return A[-K]

5. 对于一个int数组，请编写一个计数排序算法，对数组元素排序。

给定一个int数组A及数组的大小n，请返回排序后的数组。

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

class CountingSort:
    def countingSort(self, A, n):
        # write code here
        bucket = [0]*(max(A)+1)
        for i in A:
            bucket[i] += 1
        res = []
        for j in range(len(bucket)):
            if bucket[j] != 0:
                res += [j]*bucket[j]
        return res

6. 对于一个int数组，请编写一个基数排序算法，对数组元素排序。

给定一个int数组A及数组的大小n，请返回排序后的数组。

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

class RadixSort:
    def radixSort(self, A, n):
        # write code here
        bucket = [[] for l in range(10)]
        for i in range(4):
            for number in A:
                value = (number//10**i)%10
                bucket[value].append(number)
            temp = []
            for j in range(len(bucket)):
                while bucket[j]:
                    temp.append(bucket[j].pop(0))
            A = temp
        return A

7. 对于一个数组，请设计一个高效算法计算需要排序的最短子数组的长度。

给定一个int数组A和数组的大小n，请返回一个二元组，代表所求序列的长度。(原序列位置从0开始标号,若原序列有序，返回0)。保证A中元素均为正整数。

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

class Subsequence:
    def shortestSubsequence(self, A, n):
        # write code here
        left=0
        right=0
        max=A[0]
        min=A[n-1]
        for i in range(1,n):
            if A[i]>=max:
                max=A[i]
            else:
                right=i
        for j in range(n-2,-1,-1):
            if A[j]<=min:
                min=A[j]
            else:
                left=j
        if left==0 and right==0:
            return 0
        else:
            return right-left+1

8. 有一个整形数组A，请设计一个复杂度为O(n)的算法，算出排序后相邻两数的最大差值。

给定一个int数组A和A的大小n，请返回最大的差值。保证数组元素多于1个。

# -*- coding:utf-8 -*-
class Gap:
    def maxGap(self, A, n):
        # write code here
        maxVal,minVal = max(A),min(A)
        hashTable = [[maxVal,minVal,0] for i in xrange(0,n + 1)]
        for x in A:
            ind = (x - minVal) * n // (maxVal - minVal)
            hashTable[ind][2] += 1
            hashTable[ind][0] = min(hashTable[ind][0],x)
            hashTable[ind][1] = max(hashTable[ind][1],x)
        diffMax = 0
        preMax = maxVal
        for x in hashTable:
            if x[2] == 0:
                continue
            diffMax = max(x[0] - preMax,diffMax)
            preMax = x[1]
        return diffMax

9. 对于两棵彼此独立的二叉树A和B，请编写一个高效算法，检查A中是否存在一棵子树与B树的拓扑结构完全相同。

给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。

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

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class IdenticalTree:
    def chkIdentical(self, A, B):
        # write code here
        stringA = self.treeList(A)
        stringB = self.treeList(B)
        if stringB in stringA:
            return True
        else:
            return False
    def treeList(self,C):
        if C == None:
            return "#!"
        string = str(C.val)+"!"
        string += self.treeList(C.left)
        string += self.treeList(C.right)
        return string

10. 对于两个字符串A和B，如果A和B中出现的字符种类相同且每种字符出现的次数相同，则A和B互为变形词，请设计一个高效算法，检查两给定串是否互为变形词。

给定两个字符串A和B及他们的长度，请返回一个bool值，代表他们是否互为变形词。

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

class Transform:
    def chkTransform(self, A, lena, B, lenb):
        # write code here
        if lena != lenb:
            return False
        dictA = dict()
        dictB = dict()
        for cha in A:
            if cha not in dictA.keys():
                dictA[cha] = 1
            else:
                dictA[cha] += 1
        for cha in B:
            if cha not in dictB.keys():
                dictB[cha] = 1
            else:
                dictB[cha] += 1
        return dictA == dictB

11.对于一个字符串，请设计一个算法，判断其是否为一个合法的括号串。

给定一个字符串A和它的长度n，请返回一个bool值代表它是否为一个合法的括号串。

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

class Parenthesis:
    def chkParenthesis(self, A, n):
        # write code here
        num = 0
        for cha in A:
            if cha == '(':
                num += 1
            if cha == ')':
                num -= 1
            if num < 0:
                return False
        if num == 0:
            return True
        else:
            return False

12.对于一个字符串,请设计一个高效算法，找到字符串的最长无重复字符的子串长度。

给定一个字符串A及它的长度n，请返回它的最长无重复字符子串长度。保证A中字符全部为小写英文字符，且长度小于等于500。

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

class DistinctSubstring:
    def longestSubstring(self, A, n):
        # write code here
        dic = {}
        maxLength = 0
        length = 0
        pre = -1
        for i in range(n):
            if dic.has_key(A[i]):
                if dic[A[i]] > pre:
                    length = i - dic[A[i]]
                    pre = dic[A[i]]
                else:
                    length = i - pre
                maxLength = max(length, maxLength)
                dic[A[i]] = i
            else:
                length = i - pre
                dic[A[i]] = i
                maxLength = max(length, maxLength)
        return maxLength

13.定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

# -*- coding:utf-8 -*-
class Solution:
    #write code here
    def __init__(self):
        self.stackData = []
        self.stackMin = []
    def push(self, node):
        # write code here
        if not self.stackData:
            self.stackMin.append(node)
        else:
            if node >= self.stackData[-1]:
                self.stackMin.append(self.stackMin[-1])
            else:
                self.stackMin.append(node)
        self.stackData.append(node)
    def pop(self):
        # write code here
        self.stackMin.pop()
        return self.stackData.pop()
    def top(self):
        # write code here
        return self.stackData[-1]
    def min(self):
        # write code here
        return self.stackMin[-1]

13. 编写一个类,只能用两个栈结构实现队列,支持队列的基本操作(push，pop)。

给定一个操作序列ope及它的长度n，其中元素为正数代表push操作，为0代表pop操作，保证操作序列合法且一定含pop操作，请返回pop的结果序列。

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

class TwoStack:
    def __init__(self):
        self.pushStack = []
        self.popStack = []
    def twoStack(self, ope, n):
        # write code here
        res = []
        for number in ope:
            if number > 0:
                self.pushStack.append(number)
            if number == 0:
                if not self.popStack:
                    while(self.pushStack):
                        self.popStack.append(self.pushStack.pop())
                    res.append(self.popStack.pop())
                    while(self.popStack):
                        self.pushStack.append(self.popStack.pop())
        return res
                    
                        

14. 实现一个栈的逆序，但是只能用递归函数和这个栈本身的pop操作来实现，而不能自己申请另外的数据结构。

给定一个整数数组A即为给定的栈，同时给定它的大小n，请返回逆序后的栈。

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

class StackReverse:
    def reverseStack(self, A, n):
        # write code here
        if len(A) == 0:
            return
        else:
            i = self.get(A)
            self.reverseStack(A,n-1)
            A.append(i)
        return A
    def get(self,A):
        result = A.pop()
        if len(A) == 0:
            return result
        else:
            last = get(A)
            A.append(result)
            return last

15. 请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。

给定一个int[] numbers(C++中为vector&ltint>)，其中第一个元素为栈顶，请返回排序后的栈。请注意这是一个栈，意味着排序过程中你只能访问到第一个元素。

# -*- coding:utf-8 -*-
class TwoStacks:
    def twoStacksSort(self, numbers):
        # write code here
        iStack = []
        helpStack = []
        for i in range(len(numbers)-1,-1,0):
            iStack.append(numbers[i])
        while len(iStack)>0:
            currentValue = iStack.pop()
            if len(helpStack)>0:
                if currentValue>helpStack[-1]:
                    temp = len(helpStack)
                    for i in range(temp):
                        iStack.append(helpStack.pop())
                    helpStack.append(currentValue)
                    for i in range(temp):
                        helpStack.append(iStack.pop())
                else:
                    helpStack.append(currentValue)
            else:
                helpStack.append(currentValue)
        for i in range(len(numbers)):
            iStack.append(helpStack.pop())
        for i in range(len(numbers)):
            numbers[i] = iStack.pop()
        return numbers

16. 有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边,窗口每次向右边滑一个位置。 返回一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。 以数组为[4,3,5,4,3,3,6,7]，w=3为例。因为第一个窗口[4,3,5]的最大值为5，第二个窗口[3,5,4]的最大值为5，第三个窗口[5,4,3]的最大值为5。第四个窗口[4,3,3]的最大值为4。第五个窗口[3,3,6]的最大值为6。第六个窗口[3,6,7]的最大值为7。所以最终返回[5,5,5,4,6,7]。

给定整形数组arr及它的大小n，同时给定w，请返回res数组。保证w小于等于n，同时保证数组大小小于等于500。

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

class SlideWindow:
    def slide(self, arr, n, w):
        # write code here
        qmax = []
        res = []
        for i in range(n):
            while qmax != []:
                j = qmax[-1]
                if arr[j] > arr[i]:
                    break
                else:
                    qmax.pop()
            qmax.append(i)
            if i >= w-1:
                if i-qmax[0]>=w:
                    qmax.pop(0)
                res.append(arr[qmax[0]])
        return res

17. 对于一个没有重复元素的整数数组，请用其中元素构造一棵MaxTree，MaxTree定义为一棵二叉树，其中的节点与数组元素一一对应，同时对于MaxTree的每棵子树，它的根的元素值为子树的最大值。现有一建树方法，对于数组中的每个元素，其在树中的父亲为数组中它左边比它大的第一个数和右边比它大的第一个数中更小的一个。若两边都不存在比它大的数，那么它就是树根。请设计O(n)的算法实现这个方法。

给定一个无重复元素的数组A和它的大小n，请返回一个数组，其中每个元素为原数组中对应位置元素在树中的父亲节点的编号，若为根则值为-1。

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

class MaxTree:
    def maxLeft(self,A):
        dictLeft = []
        stack = []
        for i in A:
            while len(stack)!=0:
                if i>stack[-1]:
                    stack.pop()
                else:
                    dictLeft.append(stack[-1])
                    stack.append(i)
                    break
            if len(stack) == 0:
                dictLeft.append(-1)
                stack.append(i)
        return dictLeft
    def buildMaxTree(self, A, n):
        left = self.maxLeft(A)
        right = self.maxLeft(A[::-1])[::-1]
        res = []
        for i in range(n):
            if left[i] != -1:
                if right[i] != -1:
                    res.append(min(left[i],right[i]))
                else:
                    res.append(left[i])
            else:
                if right[i] != -1:
                    res.append(right[i])
                else:
                    res.append(-1)
        for i in range(n):
            if res[i] != -1:
                res[i] = A.index(res[i])
        return res

18. 有一个整数val，如何在节点值有序的环形链表中插入一个节点值为val的节点，并且保证这个环形单链表依然有序。

给定链表的信息，及元素的值A及对应的nxt指向的元素编号同时给定val，请构造出这个环形链表，并插入该值。

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

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class InsertValue:
    
    def insert(self, A, nxt, val):
        # write code here
        if not A:
            head = ListNode(val)
            head.next = head
            return head
        head = ListNode(A[0])
        pre = head
        for i in range(1,len(A)):
            n = ListNode(A[i])
            pre.next = n
            pre = pre.next
            
        #pre.next = head 
        insert = ListNode(val)
        p = head
        n = head.next
        while(n):
            if(p.val>=insert.val):
                insert.next=p
                head = insert
                break;
            if(p.val<insert.val and n.val>=insert.val):
                p.next = insert
                insert.next = n
                break;
            else:
                p=n
                n=n.next
        if not n:
            p.next = insert
        return head

19.实现一个算法，删除单向链表中间的某个结点，假定你只能访问该结点。

给定带删除的头节点和要删除的数字，请执行删除操作，返回删除后的头结点。链表中没有重复数字
C++实现

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Remove {
public:
    ListNode* removeNode(ListNode* pHead, int delVal) {
        // write code here
        if(pHead==NULL)
            return pHead;
        if(pHead->val==delVal)
        {
            ListNode *node=pHead->next;
            pHead->next=NULL;
            return node;
        }
        ListNode *pre=pHead;
        ListNode *cur=pHead->next;
        while(cur!=NULL)
        {
            if(cur->val==delVal)
            {
                pre->next=cur->next;
                cur->next=NULL;
                break;
            }
            pre=pre->next;
            cur=cur->next;
        }
        return pHead;
    }
};

20. 对于一个链表，我们需要用一个特定阈值完成对它的分化，使得小于等于这个值的结点移到前面，大于该值的结点在后面，同时保证两类结点内部的位置关系不变。

给定一个链表的头结点head，同时给定阈值val，请返回一个链表，使小于等于它的结点在前，大于等于它的在后，保证结点值不重复。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Divide:
    def listDivide(self, head, val):
        # write code here
        left,right = [],[]
        currentNode = head
        while currentNode:
            if currentNode.val > val:
                right.append(currentNode.val)
            else:
                left.append(currentNode.val)
            currentNode = currentNode.next
        left += right
        p = ListNode(left[0])
        pre = p
        for i in range(1,len(left)):
            pre.next = ListNode(left[i])
            pre = pre.next
        return p
            

21.现有两个升序链表，且链表中均无重复元素。请设计一个高效的算法，打印两个链表的公共值部分。

给定两个链表的头指针headA和headB，请返回一个vector，元素为两个链表的公共部分。请保证返回数组的升序。两个链表的元素个数均小于等于500。保证一定有公共值

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Common:
    def findCommonParts(self, headA, headB):
        # write code here
        res = []
        if headA is None and headB is None:
            return res
        a = headA
        b = headB
        while a and b:
            if a.val > b.val:
                b = b.next
            elif a.val < b.val:
                a = a.next
            else:
                res.append(a.val)
                a = a.next
                b = b.next
        return res

22.有一个单链表，请设计一个算法，使得每K个节点之间逆序，如果最后不够K个节点一组，则不调整最后几个节点。例如链表1->2->3->4->5->6->7->8->null，K=3这个例子。调整后为，3->2->1->6->5->4->7->8->null。因为K==3，所以每三个节点之间逆序，但其中的7，8不调整，因为只有两个节点不够一组。

给定一个单链表的头指针head,同时给定K值，返回逆序后的链表的头指针。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class KInverse:
    def inverse(self, head, k):
        # write code here
        count = 0
        pre = head
        
        while pre:
            count += 1
            if count == k:
                reverse(pre)
    def reverse(self,head):
        stack = []
        currentNode = head
        while currentNode:
            stack.append(currentNode.val)
            currentNode = currentValue.next
        reverse = []
        for i in range(len(stack)):
            reverse.append(stack.pop())
        p = reverse[0]
        pre = p
        for in range(1,len(reverse)):
            pre.next = ListNode(reverse[i])
            pre = pre.next
        return p

23. 现在有一个单链表。链表中每个节点保存一个整数，再给定一个值val，把所有等于val的节点删掉。

给定一个单链表的头结点head，同时给定一个值val，请返回清除后的链表的头结点，保证链表中有不等于该值的其它值。请保证其他元素的相对顺序。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class ClearValue:
    def clear(self, head, val):
        # 设计pre存放current节点之前的节点
        pre = None
        currentNode = head
        while currentNode:
            if pre == None and currentNode.val == val:
                currentNode = currentNode.next
                head = currentNode
            elif pre and currentNode.val == val:
                pre.next = currentNode.next
                currentNode = currentNode.next
            else:
                pre = currentNode
                currentNode = currentNode.next
        return head
               

24. 请编写一个函数，检查链表是否为回文。

给定一个链表ListNode* pHead，请返回一个bool，代表链表是否为回文。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Palindrome:
    def isPalindrome(self, pHead):
        # write code here
        cmpList = []
        p = pHead
        while p:
            cmpList.append(p.val)
            p = p.next
        m = pHead
        for i in range(len(cmpList)):
            if cmpList.pop() == m.val:
                m = m.next
            else:
                return False
        return True

25. 如何判断一个单链表是否有环？有环的话返回进入环的第一个节点的值，无环的话返回-1。如果链表的长度为N，请做到时间复杂度O(N)，额外空间复杂度O(1)。

给定一个单链表的头结点head（注意另一个参数adjust为加密后的数据调整参数，方便数据设置，与本题求解无关)，请返回所求值。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class ChkLoop:
    def chkLoop(self, head, adjust):
        # write code here
        if not head:
            return -1
        p,q=head,head  #p慢指针 q快指针
        while q.next and q.next.next:
            p=p.next
            q=q.next.next
            if p==q:
                break
        if not q.next or not q.next.next:
            return -1 
         #肯定有环，只是在找入环节点
        q=head
        while p!=q: 
            q=q.next
            p=p.next
        return p.val

26. 现在有两个无环单链表，若两个链表的长度分别为m和n，请设计一个时间复杂度为O(n + m)，额外空间复杂度为O(1)的算法，判断这两个链表是否相交。

给定两个链表的头结点headA和headB，请返回一个bool值，代表这两个链表是否相交。保证两个链表长度小于等于500。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class CheckIntersect:
    def chkIntersect(self, headA, headB):
        # write code here
        if not headA or not headB:
            return False
        curA = headA
        curB = headB
        n = 0
        while curA.next:
            curA = curA.next
            n += 1
        while curB.next:
            curB = curB.next
            n -= 1
        if curA != curB:
            return False
        if n > 0:
            curA = headA
        else:
            curA = headB
        if curA == headA:
            curB = headB
        else:
            curB == headA
        n = abs(n)
        while n:
            curA = curA.next
            n -= 1
        if curA == curB:
            return curA
        while curA != curB: #两个总会相等的因为最终会有None值
            curA = curA.next
            curB = curB.next
        return curA

27. 如何判断两个有环单链表是否相交？相交的话返回第一个相交的节点，不想交的话返回空。如果两个链表长度分别为N和M，请做到时间复杂度O(N+M)，额外空间复杂度O(1)。

给定两个链表的头结点head1和head2(注意，另外两个参数adjust0和adjust1用于调整数据,与本题求解无关)。请返回一个bool值代表它们是否相交。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class ChkIntersection:
    def chkInter(self, head1, head2, adjust0, adjust1):
        # write code here
        node1 = self.chkLoop(head1)
        node2 = self.chkLoop(head2)
        if not node1 or not node2:
            return False
        if  node1 == node2:
            return self.chkNonloopInter(head1,head2,node1)
        else:
            cur1 = head1
            while cur1 != node1:
                cur1 = cur1.next
            cur1 = cur1.next
            while cur1 != node1:
                cur1 = cur1.next
                if cur1 == node2:
                    return node2
            return False
    def chkLoop(self, head):
        fastNode = head
        slowNode = head
        while fastNode.next and fastNode.next.next:
            fastNode = fastNode.next.next
            slowNode = slowNode.next
            if fastNode == slowNode:
                break
        if not fastNode.next or not fastNode.next.next:
            return False
        fastNode = head
        while fastNode != slowNode:
            fastNode = fastNode.next
            slowNode = slowNode.next
        return fastNode
    def chkNonloopInter(self,headA,headB,node):
        curA = headA
        curB = headB
        n = 0
        while curA != node:
            curA = curA.next
            n += 1
        while curB != node:
            curB = curB.next
            n -= 1
        if curA != curB:
            return node
        if n > 0:
            curA = headA
        else:
            curA = headB
        if curA == headA:
            curB = headB
        else:
            curB = headA
        n = abs(n)
        while n:
            curA = curA.next
            n -= 1
        if curA == curB:
            return curA
        while curA != curB:
            curA = curA.next
            curB = curB.next
        return curA

28. 给定两个单链表的头节点head1和head2，如何判断两个链表是否相交？相交的话返回true，不想交的话返回false。

给定两个链表的头结点head1和head2(注意，另外两个参数adjust0和adjust1用于调整数据,与本题求解无关)。请返回一个bool值代表它们是否相交。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class ChkIntersection:
    def chkInter(self, head1, head2, adjust0, adjust1):
        # write code here
        node1 = self.chkLoop(head1)
        node2 = self.chkLoop(head2)
        if node1 == None and node2 == None:
            return self.chkNonloopInter(head1,head2,None)
        if (node1 == None and not node2) or (not node1 and node2 == None):
            return False
        if node1 and node2:
            return self.chkLoopInter(head1,head2,node1,node2)
    def chkLoopInter(self, head1, head2,node1,node2):
        if  node1 == node2:
            return self.chkNonloopInter(head1,head2,node1)
        else:
            cur1 = head1
            while cur1 != node1:
                cur1 = cur1.next
            cur1 = cur1.next
            while cur1 != node1:
                cur1 = cur1.next
                if cur1 == node2:
                    return node2
            return False
    def chkLoop(self, head):
        fastNode = head
        slowNode = head
        while fastNode.next and fastNode.next.next:
            fastNode = fastNode.next.next
            slowNode = slowNode.next
            if fastNode == slowNode:
                break
        if not fastNode.next or not fastNode.next.next:
            return False
        fastNode = head
        while fastNode != slowNode:
            fastNode = fastNode.next
            slowNode = slowNode.next
        return fastNode
    def chkNonloopInter(self,headA,headB,node):
        curA = headA
        curB = headB
        n = 0
        while curA != node:
            curA = curA.next
            n += 1
        while curB != node:
            curB = curB.next
            n -= 1
        if curA != curB:
            return node
        if n > 0:
            curA = headA
        else:
            curA = headB
        if curA == headA:
            curB = headB
        else:
            curB = headA
        n = abs(n)
        while n:
            curA = curA.next
            n -= 1
        if curA == curB:
            return curA
        while curA != curB:
            curA = curA.next
            curB = curB.next
        return curA

29.定义局部最小的概念。arr长度为1时，arr[0]是局部最小。arr的长度为N(N>1)时，如果arr[0]<arr[1]，那么arr[0]是局部最小；如果arr[N-1]<arr[N-2]，那么arr[N-1]是局部最小；如果0<i<N-1，既有arr[i]<arr[i-1]又有arr[i]<arr[i+1]，那么arr[i]是局部最小。 给定无序数组arr，已知arr中任意两个相邻的数都不相等，写一个函数，只需返回arr中任意一个局部最小出现的位置即可。

class Solution {
public:
    int getLessIndex(vector<int> arr) {
        if (arr.size()==0)
            return -1;
        if (arr.size()==1)
            return 0;
        int len = arr.size();
        if (arr[0]<arr[1])
            return 0;
        if (arr[len-2]>arr[len-1])
            return len-1;
        int res = getIndex(arr,1,len-2);
        return res;
    }
    int getIndex(vector<int> arr, int left, int right) {
        while(left <= right){
            int mid = (left + (right-left)/2);
            if ((arr[mid]<arr[mid-1])&&(arr[mid]<arr[mid+1]))
                return mid;
            else if (arr[mid]>arr[mid-1])
                right = mid-1;
            else
                left = mid+1; 
        }
        return -1;
    }
};

30. 对于一个有序数组arr，再给定一个整数num，请在arr中找到num这个数出现的最左边的位置。

给定一个数组arr及它的大小n，同时给定num。请返回所求位置。若该元素在数组中未出现，请返回-1。

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

class LeftMostAppearance:
    def findPos(self, arr, n, num):
        # write code here
        res = -1
        left = 0
        right = n-1
        while left<=right:
            mid = left + (right-left)/2
            if arr[mid] == num:
                res = mid
                right = mid-1
            elif arr[mid] < num:
                left = mid+1
            else:
                right = mid-1
        return res

30. 对于一个有序循环数组arr，返回arr中的最小值。有序循环数组是指，有序数组左边任意长度的部分放到右边去，右边的部分拿到左边来。比如数组[1,2,3,3,4]，是有序循环数组，[4,1,2,3,3]也是。

给定数组arr及它的大小n，请返回最小值。

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

class MinValue:
    def getMin(self, arr, n):
        # write code here
        left = 0
        right = n-1
        res = -1
        if arr[left] < arr[right]:
            return arr[left]
        while left<=right:
            if right-left==1:
                break
            mid = left + (right-left)/2
            if arr[mid]<arr[left]:
                right = mid-1
            else if arr[mid]>arr[right]:
                left = mid+1
            else:
                break
        return min(arr[left],arr[right])

31. 请用递归方式实现二叉树的先序、中序和后序的遍历打印。

给定一个二叉树的根结点root，请依次返回二叉树的先序，中序和后续遍历(二维数组的形式)。

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

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class TreeToSequence:
    def convert(self, root):
        # write code here
        ret = [[],[],[]]
        if root is None:
            return ret
        self.preorder(root,ret[0])
        self.inorder(root,ret[1])
        self.posorder(root,ret[2])
        return ret
    def preorder(self,r,arr):
        if r is None:
            return []
        arr.append(r.val)
        self.preorder(r.left,arr)
        self.preorder(r.right,arr)
    def inorder(self,r,arr):
        if r is None:
            return []
        self.inorder(r.left,arr)
        arr.append(r.val)
        self.inorder(r.right,arr)
    def posorder(self,r,arr):
        if r is None:
            return []
        self.posorder(r.left,arr)
        self.posorder(r.right,arr)
        arr.append(r.val)

32. 请用非递归方式实现二叉树的先序、中序和后序的遍历打印。

给定一个二叉树的根结点root，请依次返回二叉树的先序，中序和后续遍历(二维数组的形式)。

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

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class TreeToSequence:
    def convert(self, root):
        result = []
         
        result.append(self.pre(root, []))
        result.append(self.mid(root, []))
        result.append(self.post(root, []))
        return result
    def pre(self, root, result):
        stack = []
        if root == None:
            return stack
        stack.append(root)
        while len(stack):
            cur = stack.pop()
            result.append(cur.val)
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)
        return result
    def mid(self, root, result):
        stack = []
        if root == None:
            return stack
        cur = root
         
        while (len(stack) or cur):
             
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                result.append(cur.val)
                cur = cur.right
        return result
    def post(self, root, result):
        stack1 = []
        stack2 = []
        if root == None:
            return []
        stack1.append(root)
        while len(stack1):
            cur = stack1.pop()
            stack2.append(cur)
            if cur.left:
                stack1.append(cur.left)
            if cur.right:
                stack1.append(cur.right)
        while len(stack2):
                result.append(stack2.pop().val)
        return result

33. 首先我们介绍二叉树先序序列化的方式，假设序列化的结果字符串为str，初始时str等于空字符串。先序遍历二叉树，如果遇到空节点，就在str的末尾加上“#!”，“#”表示这个节点为空，节点值不存在，当然你也可以用其他的特殊字符，“!”表示一个值的结束。如果遇到不为空的节点，假设节点值为3，就在str的末尾加上“3!”。现在请你实现树的先序序列化。

给定树的根结点root，请返回二叉树序列化后的字符串。

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

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class TreeToString:
    def toString(self, root):
        stack = []
        res = ""
        if root is None:
            return res
        stack.append(root)
        while stack:
            cur = stack.pop()
            if cur:
                res += (str(cur.val)+"!")
                stack.append(cur.right)
                stack.append(cur.left)
            else:
                res += "#!"
        return res 

34. 有一棵二叉树，请设计一个算法判断这棵二叉树是否为平衡二叉树。

给定二叉树的根结点root，请返回一个bool值，代表这棵树是否为平衡二叉树。

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

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class CheckBalance:
    def check(self, root):
        # write code here
        if self.getHeight(root) >=0:
            return True
        else:
            return False
    def getHeight(self,root):  #后序遍历 得到层数
        if root is None:  #空树，层数为0
            return 0
        left=self.getHeight(root.left)  #左子树 深度
        right=self.getHeight(root.right)  #右子树 深度
         
        if (abs(left-right) >1):  #不是平衡二叉树
            return -1
         
        return max(left,right)+1

35. 有一棵二叉树,请设计一个算法判断它是否是完全二叉树。

给定二叉树的根结点root，请返回一个bool值代表它是否为完全二叉树。树的结点个数小于等于500。

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

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class CheckCompletion:
    def chk(self, root):
        # write code here
        if root is None:
            return True
        queue = []
        queue.append(root)
        flag = 0
        while queue:
            cur = queue.pop(0)
            if flag:
                if cur.right or cur.left:
                    return False
            if cur.right and not cur.left:
                return False
            if not cur.right:
                flag = 1
            if cur.left:
                queue.append(cur.left)
            if cur.right:
                queue.append(cur.right)
        return True

36. 请把纸条竖着放在桌⼦上，然后从纸条的下边向上⽅对折，压出折痕后再展 开。此时有1条折痕，突起的⽅向指向纸条的背⾯，这条折痕叫做“下”折痕 ；突起的⽅向指向纸条正⾯的折痕叫做“上”折痕。如果每次都从下边向上⽅ 对折，对折N次。请从上到下计算出所有折痕的⽅向。

给定折的次数n,请返回从上到下的折痕的数组，若为下折痕则对应元素为"down",若为上折痕则为"up".

# -*- coding:utf-8 -*-
class FoldPaper:
    def foldPaper(self, n):
        if n == 0:
            return None
        head = self.createTree(n)
        res = []
        res = self.inorder(head, res)
        return res
    def inorder(self,root, res):
        if root == None:
            return None
        self.inorder(root.left,res)
        res.append(root.val)
        self.inorder(root.right,res)
        return res
    def createTree(self, n):
        count = 1
        head = TreeNode("down")
        queue = []
        queue.append(head)
        while count < n:
            for i in range(2**(count-1)):
                cur = queue.pop(0)
                cur.left = TreeNode("down")
                cur.right = TreeNode("up")
                queue.append(cur.left)
                queue.append(cur.right)
            count += 1
        return head

37. 请编写一个算法，不用任何额外变量交换两个整数的值。

给定一个数组num，其中包含两个值，请不用任何额外变量交换这两个值，并将交换后的数组返回。

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

class Swap:
    def getSwap(self, num):
        # write code here
        a = num[0]
        b = num[1]
        a = a^b
        b = b^a
        a = a^b
        num = [a,b]
        return num 

38. 给定一个整型数组arr，其中有两个数出现了奇数次，其他的数都出现了偶数次，找到这两个数。要求时间复杂度为O(N)，额外空间复杂度为O(1)。

给定一个整形数组arr及它的大小n，请返回一个数组，其中两个元素为两个出现了奇数次的元素,请将他们按从小到大排列。

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

class OddAppearance:
    def findOdds(self, arr, n):
        # 大致思路：数组所有数异或后得到两个奇数的异或值
        # 因为这个异或值不为0所以其二进制数在某一个位上（k）的值肯定为1
        # 这两个奇数的二进制位的这个k位置肯定一个为0一个为1
        # 那么所有数组中的二进制的这个位置肯定是奇数
        # 遍历就可以得到其中的一个奇数
        # 之前的两个奇数异或值再异或上这个奇数就可以得到另外一个奇数

        eo = 0
        for num in arr:
            eo = eo^num
        a = eo
        i = -1
        while True:
            i += 1
            if eo&1 == 1:
                break
            eo = eo>>1
        eo1 = 0
        for num in arr:
            if (num>>i)&1 == 1:
                eo1 = eo1^num
        eo2 = 0
        eo2 = a^eo1
        return (eo1,eo2) if eo1<eo2 else (eo2,eo1)

40. 有一个矩阵map，它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，返回所有的路径中最小的路径和。

给定一个矩阵map及它的行数n和列数m，请返回最小路径和。保证行列数均小于等于100.

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

class MinimumPath:
    def getMin(self, mmap, n, m):
        # write code here
        dp = mmap
        for j in range(1,m):
            i = 0
            dp[i][j] = dp[i][j] + dp[i][j-1]
        for i in range(1,n):
            j = 0
            dp[i][j] = dp[i][j] + dp[i-1][j]
        for i in range(1,n):
            for j in range(1,m):
                dp[i][j] += min(dp[i][j-1],dp[i-1][j])
        return dp[-1][-1]

41.这是一个经典的LIS(即最长上升子序列)问题，请设计一个尽量优的解法求出序列的最长上升子序列的长度。

给定一个序列A及它的长度n(长度小于等于500)，请返回LIS的长度。

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

class LongestIncreasingSubsequence:
    def getLIS(self, A, n):
        # write code here
        dp = [0 for _ in range(n)]
        dp[0] = 1
        for i in range(1,n):
            maxTemp = dp[0]
            j = i
            while j>=0:
                if A[i] > A[j-1]:
                    dp[i] = dp[j-1]+1
                    if dp[i] > maxTemp:
                        maxTemp = dp[i]
                j -= 1
            dp[i] = maxTemp
        return max(dp[i] for i in range(n))

42. 给定两个字符串A和B，返回两个字符串的最长公共子序列的长度。例如，A="1A2C3D4B56”，B="B1D23CA45B6A”，”123456"或者"12C4B6"都是最长公共子序列。

给定两个字符串A和B，同时给定两个串的长度n和m，请返回最长公共子序列的长度。保证两串长度均小于等于300。

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

class LCS:
    def findLCS(self, A, n, B, m):
        # write code here
        dp = [[0 for _ in range(m)] for _ in range(n)]
        for i in range(n):
            if A[i] == B[0]:
                for i in range(i,n):
                    dp[i][0] = 1
                break
        for j in range(m):
            if B[j] == A[0]:
                for j in range(j,m):
                    dp[0][j] = 1
                break
        for i in range(1,n):
            for j in range(1,m):
                if A[i] == B[j]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        return dp[-1][-1]

43. 一个背包有一定的承重cap，有N件物品，每件都有自己的价值，记录在数组v中，也都有自己的重量，记录在数组w中，每件物品只能选择要装入背包还是不装入背包，要求在不超过背包承重的前提下，选出物品的总价值最大。

给定物品的重量w价值v及物品数n和承重cap。请返回最大总价值。

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

class Backpack:
    def maxValue(self, w, v, n, cap):
        # write code here
        dp = [[0 for _ in range(cap+1)] for _ in range(n+1)]
        for i in range(1,n+1):
            for j in range(1,cap+1):
                dp[i][j] = dp[i-1][j] #不拿第i件物品
                if j>=w[i-1] and dp[i-1][j-w[i-1]] + v[i-1] > dp[i][j]:
                    dp[i][j] = dp[i-1][j-w[i-1]] + v[i-1] #拿第i件物品 所以i-1件物品的重量不能超过j-w[i-1]
        return dp[-1][-1]

44. 对于两个字符串A和B，我们需要进行插入、删除和修改操作将A串变为B串，定义c0，c1，c2分别为三种操作的代价，请设计一个高效算法，求出将A串变为B串所需要的最少代价。

给定两个字符串A和B，及它们的长度和三种操作代价，请返回将A串变为B串所需要的最小代价。保证两串长度均小于等于300，且三种代价值均小于等于100。

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

class MinCost:
    def findMinCost(self, A, n, B, m, c0, c1, c2):
        # write code here
        dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
        dp[0][0] = 0
        for i in range(1,n+1):
            dp[i][0] = dp[i-1][0] + c1
        for j in range(1,m+1):
            dp[0][j] = dp[0][j-1] + c0
        for i in range(1,n+1):
            for j in range(1,m+1):
                if A[i-1] == B[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    a1 = dp[i-1][j] + c1 #删除
                    a2 = dp[i][j-1] + c0 #插入
                    a3 = dp[i-1][j-1] + c2 #替换
                    dp[i][j] = min(a1,a2,a3)
        return dp[-1][-1]
                    

45. 对于一个有序循环数组arr，返回arr中的最小值。有序循环数组是指，有序数组左边任意长度的部分放到右边去，右边的部分拿到左边来。比如数组[1,2,3,3,4]，是有序循环数组，[4,1,2,3,3]也是。

给定数组arr及它的大小n，请返回最小值。

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

class MinValue:
    def getMin(self, arr, n):
        # write code here
        low=0
        high=n-1
        if arr[low]<arr[high]:  #说明有序循环数组是从小到大排序的，第一个元素是最小值，特殊情况单独讨论
            return arr[low]
          
        # arr[low] >= arr[high]
        while low<=high:#和寻找元素最左出现的位置”这部分是一样的
            mid=low+(high-low)/2
            if arr[low]>arr[mid]:  #左一半
                high=mid
            elif arr[mid]>arr[high]:  #右一半
                low=mid+1
            else:  
#arr[low]==arr[mid]==arr[right] 特殊情况 
#只能挨个遍历，
#之前两个if最后到了一个元素的也会到达这里进行最终的判断
                cur=arr[low]
                while low<high:
                    if cur > arr[low+1]:
                        cur=arr[low+1]
                    low=low+1
                return cur

46. 有一个有序数组arr，其中不含有重复元素，请找到满足arr[i]==i条件的最左的位置。如果所有位置上的数都不满足条件，返回-1。

给定有序数组arr及它的大小n，请返回所求值。

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

class Find:
    def findPos(self, arr, n):
        # write code here
        res = -1
        if arr[0] > n-1 or arr[n-1] < 0:
            return res
        right = n-1
        left = 0
        while left<=right:
            mid = left + (right-left)/2
            if arr[mid] > mid:
                right = mid-1
            elif arr[mid] < mid:
                left = mid+1
            else:
                res = mid
                right = mid-1
        return res

47. 给定一棵完全二叉树的根节点root，返回这棵树的节点个数。如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。

给定树的根结点root，请返回树的大小。

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

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class CountNodes:
    def count(self, root):
        # write code here
        if root is None:
            return 0
        return self.bs(root,1,self.mostLeftLevel(root,1))
         
    def bs(self,node,l,h): # l为层数，h为该二叉树最左侧的层数
        #特殊情况讨论
        if l == h:
            return 1
        elif self.mostLeftLevel(node.right,l+1)==h:
            return (1<<h-l)+self.bs(node.right,l+1,h)
        else:
            return (1<<h-l-1)+self.bs(node.left,l+1,h)

    def mostLeftLevel(self,node,level):#计算最左侧二叉树的层数
        while node !=None:
            level+=1
            node=node.left
        return level-1  #层数

48. 如果更快的求一个整数k的n次方。如果两个整数相乘并得到结果的时间复杂度为O(1)，得到整数k的N次方的过程请实现时间复杂度为O(logN)的方法。

给定k和n，请返回k的n次方，为了防止溢出，请返回结果Mod 1000000007的值。

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

class QuickPower:
    def getPower(self, k, N):
        temp = k
        res = 1
        while N:
            if N&1:
                res = (res*temp) % 1000000007
            temp = (temp*temp) % 1000000007
            N >>= 1
        return res

49. 找出数组中出现次数超过一半的元素

# Method 01
def checkNumber2(arr):
    findNumber = 0
    count = 0
    for i in range(len(arr)):
        if count==0:
            findNumber = arr[i]
            count = 1
        else:
            if findNumber == arr[i]:
                count += 1
            else:
                count -= 1
    return findNumber

# Method 02

def checkNumber(arr):
    dic = {}
    for i in range(len(arr)):
        if arr[i] in dic:
            dic[arr[i]] += 1
        else:
            dic[arr[i]] = 1
    value = max(dic[arr[i]] for i in range(len(arr)))
    findIndex = list(dic.values()).index(value)
    findNumber = list(dic.keys())[findIndex]
    return findNumber

50.链表反转

思路参考 https://blog.csdn.net/gongliming_/article/details/88712221

class NodeList:
    def __init__(self, x):
        self.val = x
        self.next = None

def nodeReverse(head):
    preNode = NodeList(0)
    nextNode = NodeList(0)
    while(head):
        nextNode = head.next
        head.next = preNode
        preNode = head
        head = nextNode
    return preNode
    '''
    while(head.next):
        nextNode = head.next
        head.next = preNode
        preNode = head
        head = nextNode
    head.next = preNode
    return head
    '''

if __name__ == '__main__':
    head = NodeList(2)
    head.next = NodeList(3)
    head.next.next = NodeList(4)
    head.next.next.next = NodeList(5)
    print 'original:'
    print '{},{},{},{}'.format(head.val, head.next.val, head.next.next.val, head.next.next.next.val)
    newHead = nodeReverse(head)
    print 'reverse:'
    print '{},{},{},{}'.format(newHead.val, newHead.next.val, newHead.next.next.val, newHead.next.next.next.val)

51.判断二叉树是否对称

method1 递归法

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

def isSemi(root):
    if not root:
        return True
    return compare(root.right, root.left)

def compare(right, left):
    if not right and not left:
        return True
    if not right or not left:
        return False
    if right.val == left.val:
        if compare(right.left, left.right):
            if compare(right.right, left.left):
                return True
    return False

if __name__ == '__main__':
    root = treeNode(1)
    root.right = treeNode(2)
    root.left = treeNode(2)
    root.right.right = treeNode(3)
    root.left.left = treeNode(4)
    print isSemi(root)

method2 非递归法，层次遍历判断对否对称

class treeNode:
    def __init__(self, x):
        self.left = None
        self.right = None
        self.val = x
def isSemi(root):
    if not root:
        return True
    if not root.right or not root.left:
        return False
    l = []
    l.append(root.left)
    l.append(root.right)
    while(len(l)):
        right = l.pop(-1)
        left = l.pop(-1)
        if not right and not left:
            continue
        if not right or not left:
            return False
        if right.val == left.val:
            l.append(right.right)
            l.append(left.left)
            l.append(right.left)
            l.append(left.right)
        else:
            return False

if __name__ == '__main__':
    root = treeNode(1)
    root.right = treeNode(2)
    root.left = treeNode(2)
    root.right.right = treeNode(3)
    root.left.left = treeNode(4)
    print isSemi(root)

52.大数相加

def solve(s,t):
    if len(s) > len(t):
        n = len(s) - len(t)
        t = "{}{}".format('0'*n, t)
    elif len(s) < len(t):
        n = len(t) - len(s)
        s = "{}{}".format('0'*n, s)
    sum_list = [0 for _ in range(len(s)+1)]
    s = s[::-1]
    t = t[::-1]
    for i,number in enumerate(s):
        v_add = int(t[i]) + int(number) + sum_list[i]
        if v_add >= 10:
            sum_list[i+1] = v_add//10
            v_add = v_add%10
        sum_list[i] = v_add
        
    str_result = ''.join(str(item) for item in sum_list[::-1])
    if str_result[0] == '0':
        return str_result[1:]
    else:
        return str_result