剑指 Offer2（Python 版）解析（Ch4）

第四章：解决面试题的思路

具体实现和测试代码：

The-DataStructure-and-Algorithms/CodingInterview2-Python

系列解析（TBD）：

Python 单例模式
好玩儿的 DP
递归还是递归
双指针的威力
双列表的威力
有趣的排列组合

特别说明：下文中的实例代码一般仅包括核心算法（不一定能直接运行），完整代码可以参考对应的链接。

第四章：解决面试题的思路

画图让抽象问题形象化
举例让抽象问题具体化
把复杂问题分解成若干小问题，再递归解决小问题

面试题 27：二叉树的镜像

题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。

镜像就是左右子树互换的过程：

def mirror(tree):
    if not tree:
        return
    tree.left, tree.right = tree.right, tree.left
    if tree.left:
        mirror(tree.left)
    if tree.right:
        mirror(tree.right)
    return tree

或者用循环：

def mirror(tree):
    if not tree:
        return
    stack = [tree]
    while stack:
        node = stack.pop()
        node.left, node.right = node.right, node.left
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return tree

具体实现和测试代码可参考：27_MirrorOfBinaryTree

面试题 28：对称的二叉树

题目：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

可以定义一种先右节点再左节点的遍历方法，如果遍历结果与正常的遍历结果一样，说明是对称的。

def is_symmetrical(tree):
    return is_symmetrical_core(tree, tree)

def is_symmetrical_core(t1, t2):
    if not t1 and not t2:
        return True
    if not t1 or not t2:
        return False
    if t1.val != t2.val:
        return False
    return is_symmetrical_core(t1.left, t2.right) and 
           is_symmetrical_core(t1.right, t2.left)

下面的 core 函数其实就是同时按不同顺序做遍历。三叉树也是类似的操作，要注意的是 mid 也要比较，因为 mid 也有子树。

二叉树的具体实现和测试代码可参考：28_01_SymmetricalBinaryTree

三叉树的具体实现和测试代码可参考：28_02_SymmetricalTernaryTree

面试题 29：顺时针打印矩阵

题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

这道题看似简单，却很容易出错，尤其是一圈一圈打印矩阵时，涉及到很多边界条件的判断。比如一开始就很容易写成这样：

def print_matrix(mx):
    rows, cols = mx.shape
    start = 0
    while rows > 2 * start and cols > 2 * start:
        print_circle(mx, rows, cols, start)
        start += 1

def print_circle(mx, rows, cols, start):
    cend = cols - 1 - start
    rend = rows - 1 - start
    for i in range(start, cend+1):
        print(mx[start][i])
    for i in range(start+1, rend+1):
        print(mx[i][cend])
    for i in reversed(range(start, cend)):
        print(mx[rend][i])
    for i in reversed(range(start+1, rend)):
        print(mx[i][start])

从左到右和从上到下时应该没问题，可是最后两步的从右到左和从下到上就需要判断边界了。对于前者，要保证 start < rend，否则只有一行的矩阵就会有问题，因为 rend 和 start 都是 0，会重复打印；反之，后面这种情况则在只有一列的矩阵时有问题。修改后如下：

def print_circle(mx, rows, cols, start):
    cend = cols - 1 - start
    rend = rows - 1 - start
    for i in range(start, cend+1):
        print(mx[start][i])
    for i in range(start+1, rend+1):
        print(mx[i][cend])
    # 防止只有一行时打印
    if rend > start:
        for i in reversed(range(start, cend)):
            print(mx[rend][i])
    # 防止只有一列时打印
    if cend > start:
        for i in reversed(range(start+1, rend)):
            print(mx[i][start])

具体实现和测试代码可参考：29_PrintMatrix

面试题 30：包含 min 函数的栈

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数。在该栈中，调用 min、push 及 pop 的时间复杂度都是 O (1)。

基本思路使用两个栈，一个存储数据，一个存储最小值，新元素如果小于最小值栈内的元素，就需要同时压入两个栈，否则只压入数据栈。

class MinStack:
    def __init__(self):
        self.data_stack = []
        self.min_stack = []
    
    def minx(self):
        if self.min_stack:
            return self.min_stack[-1]
        else:
            return None
    
    def push(self, x):
        self.data_stack.append(x)
        if not self.min_stack or x < self.min_stack[-1]:
            self.min_stack.append(x)
            
    def pop(self):
        if not self.data_stack:
            return None
        else:
            x = self.data_stack.pop()
        if x == self.min_stack[-1]:
            self.min_stack.pop()
        return x

具体实现和测试代码可参考：30_MinInStack

面试题 31：栈的压入、弹出序列

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

建立一个辅助栈，记录入栈出栈过程，遍历弹出序列，逐个验证：如果下一个弹出的数字正好是栈顶元素，直接弹出；否则把没有入栈的数字压入栈，直到下个弹出的元素是栈顶元素为止。如果所有数字都入栈了，依然没有找到下一个弹出的数字，该序列就肯定不是弹出序列。

def is_pop_order(push_order, pop_order):
    stack = []
    for i in pop_order:
        if stack and stack[-1] == i:
            stack.pop()
        else:
            while push_order and push_order[0] != i:
                x = push_order.pop(0)
                stack.append(x)
            if push_order:
                push_order.pop(0)
            else:
                return False
    return True

只要知道了思路，代码写起来就比较容易了。其实基本思想就是根据入栈序列复现弹出序列。

具体实现和测试代码可参考：31_StackPushPopOrder

面试题 32（一）：不分行从上往下打印二叉树

题目：从上往下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

这个是常规题目，广度优先即可，需要维护一个 queue。

def print_tree(tree):
    queue = [tree]
    while queue:
        node = queue.pop(0)
        print(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)

具体实现和测试代码可参考：32_01_PrintTreeFromTopToBottom

面试题 32（二）：分行从上到下打印二叉树

题目：从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

这道题有很多种解法，最简单的就是在刚刚的基础上，添加层级标记。还可以直接单独打印一层，或者使用双队列。这里我们直接打印即可：

def print_tree(tree):
    queue = [tree]
    while queue:
        for i in range(len(queue)):
            node = queue.pop(0)
            print(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        print("\n")

具体实现和测试代码可参考：32_02_PrintTreesInLines

面试题 32（三）：之字形打印二叉树

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

有了上面的代码这个就很容易了，只需要隔层 reverse 一下即可。

def print_tree(tree):
    queue = [tree]
    level = 0
    while queue:
        level += 1
        tmp = []
        for i in range(len(queue)):
            node = queue.pop(0)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        if level % 2 == 0:
            tmp.reverse() # or tmp = reversed(tmp)
        if tmp:
            print(" ".join(tmp))
            print("\n")

具体实现和测试代码可参考：32_03_PrintTreesInZigzag

面试题 33：二叉搜索树的后序遍历序列

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

二叉搜索树的左节点小于根节点，右节点大于根节点。后序遍历是指先遍历左右节点，然后遍历根节点。而且后序遍历的最后一个节点是根节点。相应地，前序遍历的第一个节点是根节点，中序遍历左右两边分别是左右子树。

因此，我们可以将前 n 个比根节点小的当做左子树，后面的自然就是右子树。左右子树又可以用同样的方法确定。典型的递归操作。

def is_postorder(lst):
    root = lst[-1]
    i = 0
    for i in range(len(lst)):
        if lst[i] > root:
            break
    j = i
    for j in range(i, len(lst)):
        if lst[j] < root:
            return False
    left, right = True, True
    if i > 0:
        left = is_postorder(lst[:i])
    if j < len(lst) - 1:
        right = is_postorder(lst[j:-1])
    return left and right

有几个地方需要注意下：

边界，包括遍历的边界和递归左右子树 list 的边界
i, j 的条件判断
left, right 的初始值

具体实现和测试代码可参考：33_SquenceOfBST

面试题 34：二叉树中和为某一值的路径

题目：输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

很直接的想法是遍历所有的路径判断路径和。遍历路径自然想到前中后序遍历，由于从根节点开始，所以我们选择前序遍历。为了减少重复遍历，自然想到类似回溯法的思想。具体思路如下：

前序遍历访问节点，节点添加到路径，累加节点值
如果节点没有左右子树，判断累加和是否与输入的整数相等，相等则打印
如果有左右子树，则继续访问左右子节点；退出时则要删除当前节点，并减掉该节点的值，保证下个遍历不会包含叶节点

def find_path(tree, k):
    curr_sum = 0
    path = []
    find_path_core(tree, curr_sum, k, path)

def find_path_core(tree, curr_sum, need_sum, path):
    curr_sum += tree.val
    path.append(tree.val)
    if curr_sum == need_sum and not tree.left and not tree.right:
        print(path)
    if tree.left:
        find_path_core(tree.left, curr_sum, need_sum, path)
    if tree.right:
        find_path_core(tree.right, curr_sum, need_sum, path)
    if path:
        curr_sum -= path.pop()

最关键的不要忘记每次的 pop。具体实现和测试代码可参考：34_PathInTree

面试题 35：复杂链表的复制

题目：请实现函数 ComplexListNode* Clone (ComplexListNode* pHead)，复制一个复杂链表。在复杂链表中，每个结点除了有一个 m_pNext 指针指向下一个结点外，还有一个 m_pSibling 指向链表中的任意结点或者 nullptr。

该链表的特殊性体现在每一个节点都有一个指向任意节点的指针。最直接的想法就是把指向任意节点的那个节点存起来，这样两趟遍历即可。书中提供了另外一种思路：

每个节点后面跟一个复制的自己
节点指向任意节点的指针，下一节点也指向该任意节点的下一节点
将链表拆开即得到两份一样的链表

class ComplexNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.sibling = None

def clone_nodes(head):
    node = head
    while node:
        new = ComplexNode(node.val)
        new.next = node.next
        node.next = new
        node = new.next
    return head

def connect_sibling_nodes(head):
    node = head
    while node:
        clone = node.next
        if node.sibling:
            clone.sibling = node.sibling.next
        node = clone.next
    return head

def split_nodes(head):
    node = head
    clone_head, clone_node = None, None
    if node:
        clone_head = clone_node = node.next
        node.next = clone_node.next
        node = node.next
    while node:
        clone_node.next = node.next
        clone_node = clone_node.next
        node.next = clone_node.next
        node = node.next
    return clone_head

画个图会很直观（无论用手还是用脑子）。具体实现和测试代码可参考：35_CopyComplexList

面试题 36：二叉搜索树与双向链表

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

这道题的意思就是把二叉搜索树变成一个链表，原来的 left 和 right 就相当于链表的 parent 和 next。可以将二叉树看成三部分：左右子树和根节点，如果左右子树都排好了，用根节点连接起来自然就是需要的链表了。

def convert_bst_to_dll(tree):
    head = convert(tree, None)
    while head and head.next:
        head = head.left
    return head

def convert(head, last):
    if not head:
        return None
    curr = head
    if curr.left:
        last = convert(curr.left, last)
    
    curr.left = last
    if last:
        last.right = curr
    last = curr
    
    if curr.right:
        last = convert(curr.right, last)
    return last

有几个点需要特别注意：

要记得从 right 的 last 回到 left，判断条件也要留心，既要 head 存在，也要 next 存在
因为要的是双向链表，所以递归时务必要回指，即：last.right = curr
记得右移 last

具体实现和测试代码可参考：36_ConvertBinarySearchTree☆

面试题 37：序列化二叉树

题目：请实现两个函数，分别用来序列化和反序列化二叉树。

序列化从根节点开始，所以可以使用前序遍历。

def serialize(tree, res):
    if not tree:
        res.append("$")
        return 
    tree.append(tree.val)
    serialize(tree.left, res)
    serialize(tree.right, res)

接下来按照相反的方式反序列化：

def deserialize(res):
    head = None
    val = res.pop(0)
    if val != "$":
        head = BSN(val)
        head.left = deserialize(res)
        head.right = deserialize(res)
    return head

只要记住，反序列化正好是序列化的逆过程就好。具体实现和测试代码可参考：37_SerializeBinaryTrees

面试题 38：字符串的排列

题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串 abc，则打印出由字符 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba。

这道题有几种解法，相对简单些的就是递归了：假设字符串分成两组，第一组是第一个元素，剩余的一组。然后分成两步：

所有可能出现在第一个位置的字符，即把第一个字符和后面的交换
固定第一个字符，求后面字符的排列

# 出处：https://www.youtube.com/watch?v=KBHFyg2AcZ4
def permutate(s, l, r, res) -> list:
    if l == r - 1:
        if s not in res:
            res.append(s)
    else:
        for i in range(l, r):
            lst = list(s)
            lst[i], lst[l] = lst[l], lst[i]
            permutate("".join(lst), l+1, r, res)
            lst[l], lst[i] = lst[i], lst[l]
    return res

这里有一篇文章的图挺清楚的：Write a program to print all permutations of a given string，我就是看了这个图才彻底搞清楚的，果然是一图胜千言。还有一种类似的方法：

def permutate(s: str, moves: list, res: list):
    for i in range(len(s)):
        remain = s[0:i] + s[i+1:]
        moves.append(s[i])
        if remain:
            permutate(remain, moves, res)
        else:
            res.append("".join(moves))
        moves.pop()
    return res

此外还可以先生成所有的组合，然后剔除包含重复元素的：

def product(s, repeat):
    pools = [tuple(s)] * repeat
    result = [""]
    for pool in pools:
        result = [x+y for x in result for y in pool]
    return result

不过最简洁的方式当属下面这种，思想和上面的都差不多：

# 出处：https://www.youtube.com/watch?v=IPWmrjE1_MU
def permutate(prefix, suffix, res) -> list:
    if not suffix:
        res.append(prefix)
    else:
        for i in range(len(suffix)):
            permutate(prefix+suffix[i], suffix[:i]+suffix[i+1:], res)
    return res

最后再介绍一种相对容易理解的：

# 出处：https://www.youtube.com/watch?v=hqijNdQTBH8
def permutate6(s: str) -> list:
    lst = list(s)
    if not lst:
        return []
    elif len(lst) == 1:
        return [lst]
    else:
        res = []
        for i in range(len(lst)):
            head = lst[i]
            remain = lst[:i] + lst[i+1:]
            for p in permutate6(remain):
                res.append([head] + p)
        return res

递归的思路比较简单，关键点就两个：

第一个位置的元素
第一个位置固定后递归

用循环也可以做，itertools 中实现了这个算法，不过有点复杂，这里不再赘述了。

具体实现和测试代码可参考：38_StringPermutation☆，一共提供了 7 种方法。

Yam

Feeling, Coding, Thinking