《剑指offer—数据结构篇》题解—Python实现_剑指offer 数据结构 python

本篇博客将给出每种数据结构中的每道题的解题思路和代码注释。具体的数据结构有：链表、树、栈、队列、哈希表、列表、数组、字符串。

一、链表篇（9道题目）

涉及问题：从尾到头打印链表

                    反转链表

                    链表中倒数第K个结点

                    合并两个/K个有序链表

                    复杂链表的复制

                    删除链表中重复的结点

                    两个链表的第一个公共结点

                    链表中环的入口结点

                    二叉搜索树与双向链表

1. 从尾到头打印链表

题目描述：输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

思路：方式1：先加载链表中的所有值到新建的列表中，然后将该列表反转，返回一个ArrayList。方式2：借助辅助栈，一个栈存储链表中由前至后的结点值，另一个栈存储该栈依次弹出的结点值。

代码：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        """
        #解法1：先加载链表中的所有值到列表中，然后将该列表反转，返回一个ArrayList
        ret=[]
        head=listNode
        while(head):
            ret.append(head.val)
            head=head.next
        ret.reverse()
        return ret
        """
        #解法2：利用辅助栈来解决
        stack = []
        result_array = []
        node_p = listNode
        while node_p:
            stack.append(node_p.val)
            node_p = node_p.next 
        while stack:
            result_array.append(stack.pop(-1))
        return result_array

2.反转链表

题目描述：输入一个链表，反转链表后，输出新链表的表头。

思路：注意和第1题的区别，此题返回的是一个链表。设置None，从头指针开始依次改变指针的指向。注意：需用pHead.next作为判断条件，而非pHead，否则会导致头节点为 None，出现错误。反转链表很典型，一些链表的复杂题目是在其基础上产生的。

代码：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        #判断特殊情况
        #对于pHead的长度为1的情况依然是适用的
        if not pHead: 
            return None 
        pre = None 
        #反转指针的指向
        #这里一定要是判断pHead.next，用pHead的话pHead的头节点是None，会出现问题
        while pHead.next:
            nex = pHead.next 
            pHead.next = pre 
            pre = pHead 
            pHead = nex 
        pHead.next = pre
        return pHead

3. 链表中倒数第K个结点

题目描述：输入一个链表，输出该链表中倒数第k个结点。

思路：采用快慢指针的方式。让一个指针先走k步，当该指针到达None时，另一个指针指向该链表中的倒数第k个结点，返回该指针所对应的结点值。快慢指针的方式的题目比较重要，很多链表题目都是使用这种方法求解的。

代码：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        #考虑特殊条件
        if not head or k<=0: return None
        #快慢指针的初始位置
        fast_p = head
        slow_p = head 
        #确保可以得到与最初的fast_p位置相隔k个结点的新的新的fast_p位置
        #该位置也是和slow_p相距k个结点的位置
        for _ in range(k):
            if fast_p:
                fast_p = fast_p.next
            else:
                return None
        #由于快慢指针相距为k，设原链表的长度为n，则最终慢指针的位置为n-k+1
        #即倒数第k个结点的位置
        while fast_p:
            fast_p = fast_p.next
            slow_p = slow_p.next
        return slow_p #使用slow_p返回该节点的数值

4. 合并两个排序的链表

题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路：构建新的列表存储两个单调递增的链表的数值，对列表进行排序生成新的列表后，再由其新的生成链表。

代码：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        p1 = pHead1
        p2 = pHead2
        #新建一个链表
        l = list()  #替换为[]会导致执行的速度下降
        #加载链表的值到列表
        while p1 or p2:
            if p1:
                l.append(p1.val)
                p1 = p1.next
            if p2:
                l.append(p2.val)
                p2 = p2.next
        l.sort()
        #构建新的链表
        for i in range(len(l)):
            if i ==0:
                l3 = ListNode(l[i])
                p3 = l3
            else:
                p3.next = ListNode(l[i])
                p3 = p3.next
        #注意返回的是链表，而不是最后一个结点，因而用了l3
        return l3 if l else None 

扩展题目：合并K个排序的链表（Leetcode上面的题目）

链接：https://leetcode-cn.com/problems/merge-k-sorted-lists/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        while len(lists) > 1:
            lists.append(self.merge(lists.pop(0), lists.pop(0)))
        return lists[0] if lists else None
    def merge(self, h1, h2):
        res = head = ListNode(0)
        while h1 and h2:
            if h1.val <= h2.val: head.next, h1 = h1, h1.next
            else: head.next, h2 = h2, h2.next
            head = head.next
        #考虑指向其中一个链表中的指针已经到达该链表的None
        head.next = h1 if not h2 else h2
        return res.next

5. 复杂链表的复制

题目描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路：先复制按照指向正常结点的结点所构成的链表，再在基础上复制指向任意结点的结点所构成的链表，最终输出复杂链表。

代码：

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        #判断链表不为空
        if not pHead: return None
        p = pHead
        new_h = RandomListNode(p.label)
        pre_p = new_h
        random_map = {pHead: new_h}
        p = p.next
        #先完成对于链表的复制
        while p:
            new_p = RandomListNode(p.label)
            random_map[p] = new_p
            pre_p.next = new_p
            pre_p = pre_p.next
            p = p.next
        p = pHead
        new_p = new_h
        #然后完成对于自由结点的复制
        while p:
            random_p = p.random
            if random_p:
                new_p.random = random_map[random_p]
 
            p = p.next
            new_p = new_p.next
        #返回复杂链表
        return new_h 

6. 删除链表中的重复元素

题目描述：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

思路：依次遍历链表中的数值，将不重复结点的指针指向下一个不重复的结点，最后记得输出整个链表而非得到的链表中的最后一个结点的数值。题目很典型，类似的题目是：对于链表中的重复结点，只保留一次数值。

代码：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        dummy_head = ListNode(None) 
        dummy_head.next = pHead 
        pre = dummy_head 
        cur = pHead 
        while cur: 
            if cur.next and cur.val == cur.next.val: 
                while cur.next and cur.val == cur.next.val: 
                    cur = cur.next 
                    # cur.val != cur.next.val 
                pre.next = cur.next 
                cur = cur.next 
                continue 
            pre = pre.next 
            cur = cur.next
        #要用.next 
        return dummy_head.next

扩展题目：删除链表中的重复元素（只保留重复元素中的一个）

题目描述：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

思路：和第9题类似，只是指针指向的不同。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur = head
        while cur:
            while cur.next and cur.val == cur.next.val:
                cur.next = cur.next.next
            cur = cur.next
        #注意返回head
        return head

7. 两个链表的第一个公共结点

题目描述：输入两个链表，找出它们的第一个公共结点。

思路：方法1：两个指针循环遍历链表，指针指向的数值相同时，说明是第一个公共结点。

            方法2：找到两个链表的长度差k。让一个指针指向较长的链表的第k+1个结点，一个指针指向较短的链表的第一个结点，当指针指向的数值相同时，说明是第一个公共结点。

            注意：题目描述中的两个链表A和B自公共结点L之后的结点都是一样的。

代码：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        """
        解决方案1
        #判断条件
        if pHead1 is None or pHead2 is None:
            return None
        pa = pHead1
        pb = pHead2
        #对于两个链表，相交的第一个节点之后的部分也是相同的
        while pa != pb:
            if pa:
                pa = pa.next
            else:
                pa = pHead2
            if pb:
                pb = pb.next
            else:
                pb = pHead1
        #pa==pb对应的是相交的节点。注意这里是返回节点，因而也可以是返回pa。
        return pb
        """
        #解决方法2：采用对其最后的结点对齐的方式，使得较长的链表的
        #头结点先领先两者的长度差大小的步数，之后指针指向相同的结点值时就找到了第一个公共结点
        p1 = pHead1
        p2 = pHead2
        n_p1 = 0
        n_p2 = 0
        while p1:
            p1 = p1.next
            n_p1 += 1
        while p2:
            p2 = p2.next
            n_p2 += 1
        if n_p1 < n_p2:
            pHead1, pHead2 = pHead2, pHead1
        for _ in range(n_p1 - n_p2):
            pHead1 = pHead1.next
        while pHead1:
            if pHead1 == pHead2:
                return pHead1
            else:
                pHead1 = pHead1.next
                pHead2 = pHead2.next
        return None

8. 链表中环的入口结点

题目描述：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路：利用快慢指针。刚开始指针都指向链表的第一个结点，先找到两个指针相遇的结点值。之后，根据链表的第一个结点到环入口的步数s等于相遇点到环入口的步数(r-m)加上环的长度r的整数倍进行while判断，当满足等式约束时返回该结点的数值。具体讲解见https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/kuai-man-zhi-zhen-by-powcai-4/。

代码：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if not pHead or not pHead.next :
	        return None
        # 快慢指针 
        slow = pHead
        fast = pHead
        # 重新开始 
        start = pHead 
        while fast and fast.next: 
            slow = slow.next 
            fast = fast.next.next 
            #找到相遇点
            #根据初始点到环入口的步数s等于相遇点到环入口的步数(r-m)加上环的长度r的整数倍进行while判断
            #即s=(n-1)r+(r-m)
            if slow == fast: 
                while slow != start: 
                    slow = slow.next 
                    start = start.next 
                return slow #返回的是该节点的数值
        return None

扩展题目：判断链表是否是环形链表。题目来自Leetcode，网址：https://leetcode-cn.com/problems/linked-list-cycle/。

题目描述：给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

思路：和第8题类似，只是返回的是True或False。这里不需要满足第8题的约束条件，因为对于快慢指针而言，不是“环形链表”的话，就不会相遇。

代码：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return False
        walker = head
        runner = head.next
        try:
            while walker!=runner:
                walker = walker.next
                runner = runner.next.next
            return True
        except:
            return False

 

9. 二叉搜索树与双向链表

题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路：先进行中序遍历，然后改变链表的指针指向。本人觉得题目较难。

代码：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def treeToList(self,root):
        if not root:
            return []
        return self.treeToList(root.left)+[root]+self.treeToList(root.right)
    def Convert(self, pRootOfTree):
        # write code here
        list1=self.treeToList(pRootOfTree)
        if len(list1)==0:
            return None
        if len(list1)==1:
            return pRootOfTree
        for i in range(len(list1)-1):
            list1[i].right=list1[i+1]
            list1[i+1].left=list1[i]
        return list1[0] 

二、树篇（14道题目）

涉及问题：   重建二叉树

                    树的子结构

                    二叉树的镜像

                   从上往下打印二叉树（层序遍历，022, 060和059是类似的）                 

                   把二叉树打印成多行

                   按之字形顺序打印二叉树

                   二叉搜索树的第k个结点（中序遍历）

                   二叉搜索树的后序遍历序列（后序遍历）

                   二叉树中和为某一值的路径

                   二叉树的深度

                   平衡二叉树

                   二叉树的下一个结点

                   对称的二叉树

                   序列化二叉树

10. 重建二叉树

题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：前序遍历的第一个结点是根节点，据此和中序遍历序列可以找到根节点的左子树、右子树包含的结点，返回的结果是树的层序遍历的结果{1,2,3,4,5,6,7,8}。典型题目，注意迭代的pre和tin的取值范围。

代码：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre)==0:
            return None
        root=TreeNode(pre[0])
        TinIndex=tin.index(pre[0])
        root.left=self.reConstructBinaryTree(pre[1:TinIndex+1], tin[0:TinIndex])
        root.right=self.reConstructBinaryTree(pre[TinIndex+1:], tin[TinIndex+1:])
        return root

11. 树的子结构

题目描述：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路：依次判断A与B的left、right，判断pRoot2是否是pRoot1的子结构。

代码：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        #这里认为pRoot1和pRoot2都为空时，没法判断子结构结果，认为比较的结果是False
        #if not pRoot1 and not pRoot2:
        #    return True
        if not pRoot1 or not pRoot2:
            return False
        return self.is_subtree(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)
     
    def is_subtree(self, A, B):
        if not B:
            return True
        if not A or A.val != B.val:
            return False
        return self.is_subtree(A.left,B.left) and self.is_subtree(A.right, B.right)

12. 二叉树的镜像

题目描述：操作给定的二叉树，将其变换为源二叉树的镜像。

思路：二叉树每一层的结点进行左右交换，看得到的二叉树的结点数值是否一致。

代码：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Mirror(self, root):
        # write code here
        if not root:
            return None   
        left, right = root.left, root.right
        root.left = right
        root.right = left
        self.Mirror(root.left)
        self.Mirror(root.right)
        return root

13. 从上往下打印二叉树

题目描述：从上往下打印出二叉树的每个节点，同层节点从左至右打印。

思路：从左至右添加每一层的结点。

代码;

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回从上到下每个节点值列表
    def PrintFromTopToBottom(self, root):
        # write code here
        ret = [] 
        if root == None:
            return ret
        bfs = [root]
        while(bfs):
            tbfs = []
            for node in bfs:
                ret.append(node.val)
                if node.left:
                    tbfs.append(node.left)
                if node.right:
                    tbfs.append(node.right)
            bfs = tbfs
        return ret

14. 把二叉树打印成多行

题目描述：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

思路：注意和第13题的区别：这里是每一层输出一行（用列表表示）。因而，输出的是一个嵌套的列表。

代码：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Print(self, pRoot):
        if not pRoot:
            return []
        nodeStack=[pRoot]
        result=[]
        while nodeStack:
            res = []
            nextStack=[]
            for i in nodeStack:
                res.append(i.val)
                if i.left:
                    nextStack.append(i.left)
                if i.right:
                    nextStack.append(i.right)
            nodeStack=nextStack
            result.append(res)
        return result

15. 按照之字形顺序打印二叉树

题目描述：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

思路：和第14题类似，但是这里需要对列表中的元素的位置序号进行“奇偶判断”。注意：enumerate()结果的序号是从0开始的。

代码：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Print(self, pRoot):
        if not pRoot:
            return []
        nodeStack=[pRoot]
        result=[]
        while nodeStack:
            res = []
            nextStack=[]
            for i in nodeStack:
                res.append(i.val)
                if i.left:
                    nextStack.append(i.left)
                if i.right:
                    nextStack.append(i.right)
            nodeStack=nextStack
            result.append(res)
        returnResult=[]
        #上述代码的运行结果是[[z1],[z2],...,[zn]]，z1...zn表示对应的每一层的结点的值
        for i,v in enumerate(result):
            if i%2==0:
                returnResult.append(v)
            else:
                returnResult.append(v[::-1])
        return returnResult

16. 二叉搜索树的第K个结点

题目描述：给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。

思路：利用中序遍历实现。

代码：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 中序遍历找到第k个结点的数值
    def KthNode(self, pRoot, k):
        # write code here
        if not pRoot: return None
        stack = []
        while pRoot or stack:
            while pRoot:
                stack.append(pRoot)
                pRoot = pRoot.left
            pRoot = stack.pop()
            k -= 1
            if k == 0:
                return pRoot
            pRoot = pRoot.right

17. 二叉搜索树的后序遍历

题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路：根据二叉搜索树的性质：结点值大于结点的左结点的数值，小于结点的右结点的数值来实现。

代码：

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if len(sequence)==0:
            return False
        root = sequence[-1]
 
        i = 0
        for node in sequence[:-1]:
            if node > root:
                break
            i += 1
 
        for node in sequence[i:-1]:
            if node < root:
                return False
        left = True
        if i > 1:
            left = self.VerifySquenceOfBST(sequence[:i])
 
        right = True
        #i < (len(sequence)-1)以确保是二叉搜索树
        if (i < (len(sequence)-1))and left:
            right = self.VerifySquenceOfBST(sequence[i:-1])
        return left and right

18. 二叉树中和为某一值的路径

题目描述：输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

思路：递归，依据终止条件左结点=右结点=None且对应的根节点值是之前路径的总和中差的最后一项值。在前序、中序和后序遍历中只有前序遍历是最先访问根节点的，而且题中说在返回的list中数组长度大的数组在前，所以应该采用前序遍历的方法。前序遍历先访问左子树时，在每一个节点的根节点按照从左至右的顺序进行访问。将设定的值expectNumber与所经过的路径中除去最后一个节点的值的和进行相减，然后将结果与遍历的最后一个节点的值进行对比，如果相等的话则说明这条路径是我们所想要的，然后记录下来，返回ret。

代码：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        ret = []
        def dfs(root,sum_,tmp):
            if root:
                if root.left==None and root.right == None:
                    if root.val == sum_:
                        tmp.append(root.val)
                        ret.append(tmp[:])
                else:
                    tmp.append(root.val)
                    dfs(root.left,sum_-root.val,tmp[:])
                    dfs(root.right,sum_-root.val,tmp[:])
        dfs(root,expectNumber,[])
        return ret

19. 二叉树的深度

题目描述：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

思路：递归，求得根节点的左子树和右子树的深度，最后再加1。

代码：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if pRoot == None:
            return 0
        if pRoot.left == None and pRoot.right==None:
            return 1
        return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))+1

20. 平衡二叉树

题目描述：输入一棵二叉树，判断该二叉树是否是平衡二叉树。

思路：平衡二叉树的定义：是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。根据定义来直接判断。

代码：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if pRoot == None:
            return True
        if abs(self.TreeDepth(pRoot.left)-self.TreeDepth(pRoot.right)) > 1:
            return False
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
       
    def TreeDepth(self, pRoot):
        # write code here
        if pRoot == None:
            return 0
        nLeft = self.TreeDepth(pRoot.left)
        nRight = self.TreeDepth(pRoot.right)
        return max(nLeft+1,nRight+1)#(nLeft+1 if nLeft > nRight else nRight +1)

21. 二叉树的下一个结点

题目描述：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路：判断结点是左、右结点，然后按照中序遍历的先左结点，后父结点，最后右结点的顺序遍历下一个结点。

代码：

# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def GetNext(self, pNode):
        # write code here
        if not pNode: return None
        p = pNode
        if pNode.right:  # 有右子树
            p = pNode.right
            while p.left:
                p = p.left
            return p
         # 没有右子树
        while pNode.next and pNode.next.right == pNode:
            pNode = pNode.next
        return pNode.next

22.  对称的二叉树

题目描述：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路：递归判断。注意和第12题的区别，这里不是生成一个镜像的二叉树，而是判断已有的二叉树是否是对称的。

代码：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None        
class Solution:
    def isSymmetrical(self, pRoot):
        # write code here
        def is_same(p1,p2):
            if not p1 and not p2:
                return True
            if (p1 and p2) and p1.val==p2.val:
                return is_same(p1.left,p2.right) and is_same(p1.right,p2.left)
            return False
        if not pRoot:
            return True
        if pRoot.left and not pRoot.right:
            return False
        if not pRoot.left and pRoot.right:
            return False
        return is_same(pRoot.left,pRoot.right)

23. 序列化二叉树

题目描述：请实现两个函数，分别用来序列化和反序列化二叉树。二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以！表示一个结点值的结束（value!）。二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

思路：序列化的过程：按照层序遍历的方式查找空节点，然后由“#”进行替换。反序列化的过程：查找不是“#”的结点值，然后添加，否则是None。

代码：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.index = -1
 
    def Serialize(self, root):
        # write code here
        if root:
            return str(root.val) + ' ' +\
                self.Serialize(root.left) + \
                self.Serialize(root.right)
        else:
            return '# '
 
    def Deserialize(self, s):
        # write code here
        l = s.split()
        self.index += 1
        if self.index >= len(s): 
            return None
        
        if l[self.index] != '#':
            root = TreeNode(int(l[self.index]))
            root.left = self.Deserialize(s)
            root.right = self.Deserialize(s)
        else:
            return None
        return root

 

三、栈篇（4道题）

涉及问题：用两个栈实现队列

                    包含main函数的栈

                    栈的压入、弹出序列

                    翻转单词顺序列（栈）

24. 用两个栈来实现队列

题目描述：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

思路：和第1题类似。

代码：

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
 
    def push(self, node):
        # write code here
        self.stack1.append(node)
 
 
    def pop(self):
        # return xx
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop(-1))
        return self.stack2.pop(-1)

25. 包含min函数的栈

题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

思路：将每个node的值放到栈1中，将每个Node的值同栈2的最小值（栈2的最顶部的元素值）的对比找到最新的最小值。

代码：

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.min_stack = []  #辅助栈
    
    #保证push后的栈的顶部元素是最小的数值
    def push(self, node):
        # write code here
        self.stack.append(node)
        if not self.min_stack:
            self.min_stack.append(node)
        else:
            if self.min_stack[-1] < node:
                self.min_stack.append(self.min_stack[-1])
            else:
                self.min_stack.append(node)
                
    def pop(self):
        # write code here
        self.stack.pop(-1)
        self.min_stack.pop(-1)
        
    #self.stack的最顶上元素
    def top(self):
        # write code here
        return self.stack.pop(-1)
    
    #self.min_stack的最顶上元素
    def min(self):
        # write code here
        return self.min_stack[-1]

26. 栈的压入、弹出序列

题目描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路：找到第一个出栈的元素在压栈结果中的顺序，依次找到第2,3...。最后，判断压入栈的栈是否为空，为空则说明是弹出序列。

代码：

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        stack = []
        i = 0
        for v in pushV:
            stack.append(v)
            #满足压入即弹出时，while循环的条件为真；
            #如果不满足条件的话，继续压入新的元素，直到满足while循环的条件
            while stack and stack[-1] == popV[i]: 
                i += 1
                stack.pop(-1)
        #压入和弹出完毕后，看栈是否为空，如果为空的话，就说明是弹出完成了，即为弹出序列
        if not stack:
            return True
        else:
            return False

27. 翻转单词顺序列

题目描述：牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

思路：以""为分隔符，然后翻转，最后以""为分隔符。

代码：

# -*- coding:utf-8 -*-
class Solution:
    def ReverseSentence(self, s):
        # write code here
        stack = [n for n in s.split(' ')]
        stack.reverse()
        return ' '.join(stack)

四、队列篇（1道题）

涉及问题：滑动窗口的最大值

28. 滑动窗口的最大值

题目描述：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

思路：更新窗口内的最大值的下标，保留窗口内的最大值。

代码：

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if size == 0: return []
        queue = []
        res = []
        for i in range(len(num)):
            while queue and queue[0] <= i-size:
                queue.pop(0)
            # 挤走较小的数值
            while queue and num[queue[-1]] < num[i]:
                queue.pop(-1)
            queue.append(i)
            if i < size - 1: 
                continue
            res.append(num[queue[0]])
        return res

五、哈希表、列表、数组、矩阵、字符串篇（13道题）

涉及问题：   第一个只出现一次的字符

                    数组中的重复的数字

                    字符串流中第一个不重复的字符

                    数组中只出现一次的数字

                    调整数组顺序使奇数位于偶数前面

                    数组中出现次数超过一半的数字

                    把数组排成最小的数

                    顺时针打印矩阵

                    把字符串转换为整数

                    表示数值的字符串

                    左旋转字符串(矩阵翻转)

                    替换空格

                    正则表达式匹配(我用的暴力)  (自己不是特别懂)

29. 第一个只出现一次的字符

题目描述：在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）。

思路：遍历字符串的所有字符，将字符和对应的出现次数构成“键值对”。再次遍历，找到第一个值为1的键，即为所求的字符。

代码：

# -*- coding:utf-8 -*-
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        #采用字典的方式
        map = {}
        for i in range(len(s)):
            #字典的.get(key，value)方法对字典中没有的key赋一个value值，因而这里需要指定value值；
            #如果不指定，使用.get(key)得到字典中已有的的对应于key的value值
            map[s[i]] = map.get(s[i], 0) + 1
        for i in range(len(s)):
            if map[s[i]] == 1:
                return i
        return -1

30. 数组中重复的数字

题目描述：
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

思路：和第29题类似，这里使用列表存储数字出现的次数。

代码：

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        map = [0] * 1000
        for n in numbers:
            if map[n] == 1:
                duplication[0] = n
                return True
            else:
                map[n] = 1
        return False

31. 字符流中第一个不重复的字符

题目描述：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。如果当前字符流没有存在出现一次的字符，返回#字符。

思路：用列表来实现栈，栈中只保留连续字符中不重复的字符。

代码：

# -*- coding:utf-8 -*-
class Solution:
    # 返回对应char
    def __init__(self):
        self.data = []
    def FirstAppearingOnce(self):
        # write code here
        return self.data[0] if self.data else '#'
    def Insert(self, char):
        # write code here
        n = len(self.data)
        for i in range(n-1, -1, -1):
            if self.data[i] == char:
                self.data.pop(i)
                return
        self.data.append(char)

32. 数组中只出现一次的数字

题目描述：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路：和第29题类似。

代码：

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        map = {}
        res = []
        for n in array:
            map[n] = map.get(n, 0) + 1
        for n in array:
            if map[n] == 1:
                res.append(n)
        return res

33. 调整数组顺序使奇数位于偶数前面

题目描述：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路：统计得到数组的长度，然后将奇数依次放在前半部分，偶数也类似。

代码：

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        odd_cnt = 0
        res = [0] * len(array)
        # 统计个数
        for n in array:  
            if n % 2 != 0:
                odd_cnt += 1
        # 填坑
        odd_i = 0
        even_i = odd_cnt
        for i in range(len(array)):
            if array[i] % 2 != 0:  
                res[odd_i] = array[i]
                odd_i += 1
            else:
                res[even_i] = array[i]
                even_i += 1
        return res

34. 数组中出现次数超过数组长度一半的数字

题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,

4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

思路：找到出现次数最多的那个数字，然后判断其出现的次数是否超过数组长度的一半。

代码：

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        res = None
        cnt = 0
        # 留下数组中出现次数最高的数
        for i in numbers:  
            if not res:
                res = i
                cnt = 1
            else:
                if i == res:
                    cnt += 1
                else:
                    cnt -= 1
                    if cnt == 0:
                        res = None
        # 判断次数是否大于一半
        cnt = 0 
        for i in numbers:
            if i == res:
                cnt += 1
        if cnt > len(numbers) / 2:
            return res
        else:
            return 0

35. 把数组排成最小的数

题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

思路：首先，找到数组中元素的最大长度n。然后，将数组中的其它元素按照元素+元素最后一位（补至第n-1位）+元素在数组中的序号的形式改写。最后，对补齐后的结果进行排序，找到最小的元素，并找到其所对应的原数组的元素值，把它作为所能组成的数字的最高几位，依次按照这种方式将数组中的数字排列在一起构成最小的数字。本人觉得本题较难！

代码：

# -*- coding:utf-8 -*-
#计算数组中的数字的长度
def number_len(n):
    res = 0
    while n:
        n //= 10
        res += 1
    return res
 
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        #考虑特殊情况
        if not numbers:
            return ""
        if len(numbers) == 1: return numbers[0]
        #补齐数字的长度
        #例如：{3, 32, 321}补齐成{3331, 3222, 3213}，{1, 11, 111}补齐成{1111, 1112, 1113}
        max_len = number_len(max(numbers))
        map = {}
        for i in range(len(numbers)):
            n = numbers[i]
            pad = n % 10
            n_len = number_len(n)
            for j in range(max_len-n_len):
                n = n*10+pad
            map[n*10+n_len] = i
        #对补齐后的结果进行排序，找到最小的元素，然后根据原每个数组中的数字的长度乘以10的指数次方
        keys = sorted(map.keys())
        res = numbers[map[keys[0]]]
        for i in range(1, len(keys)):
            n = numbers[map[keys[i]]]
            res = res * 10 ** number_len(n) + n
        return res

36. 顺时针打印矩阵

题目描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10。

思路：依次打印，注意停止条件。

代码：

# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here
    # write code here
        walked = [[False] * (len(matrix[0])+1) for _ in range(len(matrix)+1)]
        for j in range(len(walked[-1])):
            walked[-1][j] = True
        for i in range(len(walked)):
            walked[i][-1] = True
        len_row = len(matrix) - 1
        len_col = len(matrix[0]) - 1
        res = []
        i = 0
        j = 0
        direction = 0  # 0向右，1向下，2向左，3向上
 
        while not walked[i][j]:
            res.append(matrix[i][j])
            walked[i][j] = True
            if direction == 0: # right
                if j < len_col and not walked[i][j+1]:
                    j += 1
                else:
                    direction = 1
                    i += 1
            elif direction == 1: # down
                if i < len_row and not walked[i+1][j]:
                    i += 1
                else:
                    direction = 2
                    j -= 1
            elif direction == 2:  # left
                if j > 0 and not walked[i][j-1]:
                    j -= 1
                else:
                    direction = 3
                    i -= 1
            elif direction == 3:  # up
                if i > 0 and not walked[i-1][j]:
                    i -= 1
                else:
                    direction = 0
                    j += 1
        return res

37. 把字符串转变为整数

题目描述：将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。输入一个字符串,包括数字字母符号,可以为空。如果是合法的数值表达则返回该数字，否则返回0。

思路：判断首字符是“+”/"-"。然后，判断其它字符的ASCII/Unicode码是否在“0”和“9”所对应的数值的大小范围之内，如果是的话说明是数字，进行转变后加到整数的对应位上。

代码：

# -*- coding:utf-8 -*-
class Solution:
    def StrToInt(self, s):
        # write code here
        res = 0
        flag = 1
        for i in range(len(s)):
            #判断数值是正是负
            if i == 0 and s[i] == '+':
                continue
            elif i == 0 and s[i] == '-':
                flag = -1
                continue
            #将每个字符转换为i“二进制”的表示结果
            #返回对应的ASCII数值，或者Unicode数值，如果所给的Unicode
            #字符超出了你的Python定义范围，则会引发一个TypeError的异常。
            n = ord(s[i]) - ord('0')
            if n>=0 and n<=9:
                res = 10 * res + n
            else:
                return False
        return res * flag

38. 显示数值的字符串

题目描述：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

思考：考虑不表示数值的字符串的情况，然后逐个进行判断。

代码：

# -*- coding:utf-8 -*-
class Solution:
    # s字符串
    def isNumeric(self, s):
        # write code here
        sign, point, hasE = False, False, False
        for i in range(len(s)):
            if s[i].lower() == 'e':
                #不出现两个'e'
                if hasE: return False
                #不能使得字符串的最后一个字符是'e'
                if i == len(s)-1: return False
                hasE = True
            elif s[i] == '+' or s[i] == '-':
                #不能同时出现'e'和'+'或'-'
                if sign and s[i-1].lower() != 'e': return False
                if not sign and i > 0 and s[i-1].lower() != 'e': return False
                sign = True
            elif s[i] == '.':
                #不出现连续的'.'
                #不能既有'.',又有'e'
                if hasE or point: return False
                point = True
            #不出现0~9之外的其它字符
            elif ord(s[i]) < ord('0') or ord(s[i]) > ord('9'):
                return False
        return True

39. 左旋转字符串

题目描述：汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

思路：对于一个字符串XY，在X与Y的交界处循环左移，使得结果为YX。可以先得到YTXT(T表示翻转，XT表示对X进行翻转)，再得到YTX，最后得到YX。

代码：

# -*- coding:utf-8 -*-
def reverse(str, s, e):
    e -= 1
    while s < e:
        str[s], str[e] = str[e], str[s]
        s += 1
        e -= 1
        
class Solution:
    def LeftRotateString(self, s, n):
        # write code here
        if len(s) == 0 or n == 0: return s
        s = list(s)
        #对于一个字符串XY，在X与Y的交界处循环左移，使得结果为YX
        #可以先得到YTXT(T表示翻转，XT表示对X进行翻转)，再得到YTX，最后得到YX
        reverse(s, 0, n)
        reverse(s, n, len(s))
        reverse(s, 0, len(s))
        return ''.join(s)

40. 替换空格

题目描述：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

思考：找到“”并进行替换，利用列表的特性。

代码：

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        s = list(s)
        count=len(s)
        for i in range(0,count):
            if s[i]==' ':
                s[i]='%20'
        return ''.join(s)

41. 正则表达式匹配

题目描述：请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。

思路：分不同的情况进行罗列。本人觉得题目较难。

代码：

# -*- coding:utf-8 -*-
class Solution:
    # s, pattern都是字符串
    def match(self, s, pattern):
        # 如果s与pattern都为空，则True
        if len(s) == 0 and len(pattern) == 0:
            return True
        # 如果s不为空，而pattern为空，则False
        elif len(s) != 0 and len(pattern) == 0:
            return False
        # 如果s为空，而pattern不为空，则需要判断
        elif len(s) == 0 and len(pattern) != 0:
            # pattern中的第二个字符为*，则pattern后移两位继续比较
            if len(pattern) > 1 and pattern[1] == '*':
                return self.match(s, pattern[2:])
            else:
                return False
        # s与pattern都不为空的情况
        else:
            # pattern的第二个字符为*的情况
            if len(pattern) > 1 and pattern[1] == '*':
                # s与pattern的第一个元素不同，则s不变，pattern后移两位，相当于pattern前两位当成空
                if s[0] != pattern[0] and pattern[0] != '.':
                    return self.match(s, pattern[2:])
                else:
                    # 如果s[0]与pattern[0]相同，且pattern[1]为*，这个时候有三种情况
                    # pattern后移2个，s不变；相当于把pattern前两位当成空，匹配后面的
                    # pattern后移2个，s后移1个；相当于pattern前两位与s[0]匹配
                    # pattern不变，s后移1个；相当于pattern前两位，与s中的多位进行匹配，因为*可以匹配多位
                    return self.match(s, pattern[2:]) or self.match(s[1:], pattern[2:]) or self.match(s[1:], pattern)
            # pattern第二个字符不为*的情况
            else:
                if s[0] == pattern[0] or pattern[0] == '.':
                    return self.match(s[1:], pattern[1:])
                else:
                    return False