61-66题

61、调整数组顺序使奇数位于偶数前面
最简单一个数组存偶数一个数组存奇数再合并，稍微快一点的写个冒泡排序O(n^2)。还可以用其它时间复杂度低一些的排序(O(nlogn))，但是要稳定的排序。现在还不会，过几天写

62、包含最小元素的栈
比较简单，记录下最小值就可以了。写的时候发现个问题，当调用pop后如果把最小值pop了的话，就会出问题。所以改了一下用列表去记录最小值

# -*- coding:utf-8 -*-
class Solution:

    def __init__(self):
        self.stack = []
        self.small = []

    def push(self, node):
        # write code here
        self.stack.append(node)
        if not self.small:
            self.small.append(node)
        else:
            for index in range(len(self.small)):
                if node < self.small[index]:
                    self.small.insert(index, node)
                    break
            else:
                self.small.append(node)

    def pop(self):
        # write code here
        temp = self.stack[-1]
        print(temp)
        print(self.stack)
        print(self.small)
        self.stack = self.stack[:-1]
        self.small.remove(temp)
        return temp

    def top(self):
        # write code here
        return self.stack[-1]

    def min(self):
        # write code here
        if not self.small:
            return None
        return self.small[0]

63、二叉树中值为某一值的路径
代码写了很长，先把所有的路径求出来再判断是否等于该值最后按长度排序

class Solution(object):

    def FindPath(self, root, expectNumber):

        def binaryTreePaths(root):
            if not root:
                return []
            queue = [[root]]
            rst = []
            while queue:
                temp = queue.pop(0)
                if not temp[-1].left and not temp[-1].right:
                    rst.append(temp)
                else:
                    if temp[-1].left:
                        temp1 = temp[:]
                        temp1.append(temp[-1].left)
                        queue.append(temp1)
                    if temp[-1].right:
                        temp2 = temp[:]
                        temp2.append(temp[-1].right)
                        queue.append(temp2)
            for i in range(len(rst)):
                rst[i] = [x.val for x in rst[i]]
            return rst

        allpath = binaryTreePaths(root)
        temp = []
        for i in allpath:
            if sum(i) == expectNumber:
                i.append(len(i))
                temp.append(i)
        sort_temp = sorted(temp, key=lambda x:x[-1], reverse=True)
        return [x[:-1] for x in sort_temp]

64、从上往下打印二叉树的节点

class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        if not root:
            return []
        queue = [root]
        rst = [root]
        while queue:
            temp = queue.pop(0)
            if temp.left:
                rst.append(temp.left)
                queue.append(temp.left)
            if temp.right:
                rst.append(temp.right)
                queue.append(temp.right)
        return [x.val for x in rst]

65、二叉搜索树的后序遍历序列
后序遍历时最后一个节点为根节点，左半边的节点比根节点小，右半边的节点比根节点打，递归判断

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        def verify(sequence):
            if not sequence:
                return False
            root = sequence[-1]
            for i in range(len(sequence)):
                if sequence[i] > root:
                    break
            for j in sequence[i:]:
                if j < root:
                    return False
            l = sequence[:i]
            r = sequence[i:-1]
            left = True
            if i > 0:
                left = verify(l)
            right = True
            if i < len(sequence)-1 and left:
                right = verify(r)
            return right
        return verify(sequence)

66、栈的压入弹出序列
虽然给我两个序列我能判断出来，但想了一会不知道如何用代码实现。只好参考别人的思路
https://blog.csdn.net/Jillian_sea/article/details/80339471

class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        if not (pushV and popV and len(pushV) == len(popV)):
            return False
        i=0
        top=0
        while pushV:
            key = self.find(pushV,popV[i])
            if not (type(key) == int) :
                return False
            if key >= top :
                del pushV[key]
                if key>0:
                    top = key-1
                else:
                    top = 0
                i += 1
            else:
                return False
        return True

    def find(self,stack,node):
        if not stack:
            return False
        for i in range(0,len(stack)):
            if stack[i] == node :
                return i
        return False