剑指offer【30~39】

题目链接：

剑指offer 30-39

30. 包含 min 函数的栈
 31. 栈的压入、弹出序列
 32.1 从上往下打印二叉树
 32.2 把二叉树打印成多行
 32.3 按之字形顺序打印二叉树
 33. 二叉搜索树的后序遍历序列
 34. 二叉树中和为某一值的路径
 35. 复杂链表的复制
 36. 二叉搜索树与双向链表
 37. 序列化二叉树
 38. 字符串的排列
 39. 数组中出现次数超过一半的数字

Python 实现：

30. 包含 min 函数的栈

除了存储数据的栈 stack，再定义一个最小栈 minstack。minstack 的长度和 stack 保持同步，只不过其是一个递减栈。如 stack = [6,7,4,5,3,8]，则 minstack = [6,6,4,4,3,3]。这样，在 pop 的时候，同时 pop 两个栈，不会因为删除最小值而在 minstack 中找不到。

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

31. 栈的压入、弹出序列

使用一个栈 stack 模拟压入操作；先遍历压入序列，将没有在弹出序列中遇到的数字存入 stack 中；然后再遍历弹出序列，判断是否和 stack 中序列相同。时间复杂度和空间复杂度均为 O(n)。

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        stack = []
        j = 0
        for i in range(len(pushV)):
            if pushV[i] != popV[j]:
                stack.append(pushV[i])
            else:
                j += 1
        while stack:
            if stack[-1] != popV[j]:
                return False
            stack.pop()
            j += 1
        return True

32.1 从上往下打印二叉树

二叉树的层次遍历，使用队列即可。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        if not root:
            return []
        q = collections.deque()
        ans = []
        q.append(root)
        while q:
            addr = q.popleft()
            ans.append(addr.val)
            if addr.left:
                q.append(addr.left)
            if addr.right:
                q.append(addr.right)
        return ans

32.2 把二叉树打印成多行

同 32.1，使用队列。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        ans = []
        if not pRoot:
            return []
        q = collections.deque()
        ans = []
        q.append(pRoot)
        while q:
            lens = len(q)  # 每一层有 lens 个数
            if lens > 0:   # 该层有数
                ans.append([])
            while lens > 0:
                addr = q.popleft()
                lens -= 1
                ans[-1].append(addr.val)
                if addr.left:
                    q.append(addr.left)
                if addr.right:
                    q.append(addr.right)
        return ans

32.3 按之字形顺序打印二叉树

同 32.2，使用一个标记 flag，初始为 1，每过一层翻转 flag 的值。如果 flag = 0，说明某层要从右到左打印，则将该层的打印结果翻转存入结果中。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
class Solution:
    def Print(self, pRoot):
        # write code here
        ans = []
        if not pRoot:
            return []
        q = collections.deque()
        ans = []
        q.append(pRoot)
        flag = 1
        while q:
            lens = len(q)  # 每一层有 lens 个数
            if lens > 0:   # 该层有数
                ans.append([])
            while lens > 0:
                addr = q.popleft()
                lens -= 1
                ans[-1].append(addr.val)
                if addr.left:
                    q.append(addr.left)
                if addr.right:
                    q.append(addr.right)
            if flag == 0:  # flag = 0 时翻转该层
                ans[-1].reverse()
            flag = not flag
        return ans

33. 二叉搜索树的后序遍历序列

一个二叉搜索树BST满足： max(左子树) < 根节点 < min(右子树)；
对于空数组，应该返回 False。
题目给出的是一个后序遍历，那么序列的最后一个元素就应该是根节点；
从BST的定义出发，遍历整个序列，找到第一个大于根节点的元素k，k以前的元素属于左子树，从k开始到根节点之前的元素属于右子树；
判断右子树是否都比根节点要大，如果不是，直接返回 False。
如果遍历整个序列之后得到的左右子树都满足BST的定义，则递归判断左子树和右子树是否满足BST定义。

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        lens = len(sequence)
        # 空数组返回 False
        if lens == 0:
            return False
        root = sequence[-1]
        # 找到大于 root 的第一个元素
        ind = 0
        while ind < lens - 1:
            if sequence[ind] > root:
                break
            ind += 1
        # 先判断一下右子树是不是都比根大（左子树在上一个循环已经判断过了）
        i = ind + 1
        while i < lens - 1:
            if sequence[i] < root:
                return False
            i += 1
        # 递归判断左右子树是否都满足 BST
        left = right = True  # 这里的初始值都要设置为 True，不然永远不可能为 True
        if ind > 0:  # 防止为空数组
            left = self.VerifySquenceOfBST(sequence[:ind])
        if ind < lens - 1:  # 防止为空数组
            right = self.VerifySquenceOfBST(sequence[ind:-1])
        return left and right

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

树的深搜，使用 dfs 回溯法，当到达根且目标值为 0 时找到一条路径。
在递归左右子树的过程中，如果发现提前到达根节点或者目标值为负，要进行剪枝。

# -*- 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
        def dfs(root, expectNumber, path):
            if not root and expectNumber == 0:  # 找到一条路径
                ans.add(tuple(path))
                return
            if not root or expectNumber < 0:  # 减枝
                return
            dfs(root.left, expectNumber - root.val, path + [root.val]) 
            dfs(root.right, expectNumber - root.val, path + [root.val]) 
        
        ans = set()  # 使用 set 不是 list 防止同一路径输出两次
        if not root:  # 防止 root 为空且 expectNumber 为 0 时输出 [[]] 而不是 []
            return list(ans)
        dfs(root, expectNumber, [])
        return list(ans)

35. 复杂链表的复制

分三步：
（1）遍历链表，复制 next 域；
（2）遍历链表，复制 random 域（注意一个节点的 random 域可能为 None，因此在复制的过程中要判断是否为空）；
（3）拆分两个链表（不能只拆分复制后的链表，会报错，两个都要拆出来）。

# -*- 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
        cur = pHead  # 1 复制 next
        while cur:
            co = RandomListNode(cur.label)
            co.next = cur.next
            cur.next = co
            cur = cur.next.next
        cur = pHead  # 2 复制 random
        while cur:
            if cur.random:  # 一个节点的 random 域可能为空
                cur.next.random = cur.random.next
            cur = cur.next.next
        cur, pCloneHead = pHead, pHead.next # 3 拆分两链表
        while cur.next:
            nex_ = cur.next
            cur.next = nex_.next
            cur = nex_
        return pCloneHead

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

设置一个 pre 指向链表的前一个结点，初始值为 None。使用中序遍历，每次让当前结点左指针连接上一个结点 pre，pre 的右指针连接当前结点。具体做法：

（1）遍历左子树，找到第一个结点，并设置为链表头部；
（2）当前结点的左指针连接上一个结点，pre 的右指针连接当前结点，并修改 pre 指向当前结点；
（3）遍历右子树。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        def inorder(root):
            if not root:
                return
            inorder(root.left) # 中序遍历：遍历左子树
            if not self.head:  # 链表头部
                self.head = root
            root.left = self.pre  # 连接左指针
            if self.pre:  # 连接右指针
                self.pre.right = root
            self.pre = root  # 修改上一个指针
            inorder(root.right)  # 中序遍历：遍历右子树
        
        self.pre = self.head = None  # 变量要加 self，如果是 list 则可以不用
        inorder(pRootOfTree)
        return self.head

37. 序列化二叉树

这里使用前序遍历对树序列化，然后对应的反序列化也要采取前序遍历才能恢复。在反序列化时，每次从列表中删除一个结点，遇到 "#" 要返回。之后按照前序遍历构造即可。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        if not root:
            return "#"
        return str(root.val) + "!" + self.Serialize(root.left) + "!" + self.Serialize(root.right)
        
    def Deserialize(self, s):
        # write code here
        def preorder():
            if not li:
                return None
            val = li.pop(0)  # 每次都从 list 中删除一个结点
            if val == "#":
                return None
            root = ListNode(int(val))
            root.left = preorder()
            root.right = preorder()
            return root
            
        li = s.split("!")
        return preorder()

38. 字符串的排列

回溯法，很坑，答案竟然要求返回的 list 的顺序要和参考答案的顺序一致，醉了...（本来一个 set 就搞定了，还需要增加点时间复杂度）

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        def dfs(k, path):
            if k == lens and path not in ans:
                ans.append(path)
                return
            for i in range(lens):
                if flag[i] == 0:
                    flag[i] = 1
                    dfs(k + 1, path + ss[i])
                    flag[i] = 0
        
        lens = len(ss)
        if lens == 0:
            return []
        flag = [0] * lens
        ans = []
        dfs(0, "")
        return ans

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

这道题可以使用 LeetCode精讲：摩尔投票算法，使得时间复杂度为 O(n)，空间复杂度为 O(1)。

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if not numbers:
            return 0
        pre, cnt = numbers[0], 1   # pre 记录出现次数多的那个数字
        for i in range(1, len(numbers)):
            if cnt == 0:
                pre = numbers[i]
                cnt += 1
            elif pre == numbers[i]:
                cnt += 1
            elif pre != numbers[i]:
                cnt -= 1
        # pre 是否超过了一半
        return pre if numbers.count(pre) > len(numbers) // 2 else 0

剑指 offer 终于过了一遍，大多数题目还是很简单的，但是题目具有代表性，涉及链表、数组、深搜回溯、字符串、数组、数学、位运算、动态规划等。这里做一个总结：

剑指offer【03~09】
剑指offer【10~19】
剑指offer【20~29】
剑指offer【30~39】
剑指offer【40~49】
剑指offer【50~59】
剑指offer【60~68】

剑指offer【30~39】

题目链接：

目录：

Python 实现：