解决面试题的思路

Q. 二叉树的镜像：输入一棵二叉树，输出它的镜像

1
2
3

   8         8
 6   10   10   6
5 7 9 11 11 9 7 5

A. 思路：

镜像的本质在于对每个非叶子节点交换左右子树；
从根节点出发，交换左右子树；
如果节点为空，或者已经递归到叶子节点，则递归终止

def MirrorTree(rt: TreeNode):
    if rt == None or rt.left == None and rt.right == None:
        return

    tmp = rt.left
    rt.left = rt.right
    rt.right = tmp
    if rt.left != None:
        MirrorTree(rt.left)
    if rt.right != None:
        MirrorTree(rt.right)

Q. 对称二叉树：判断一棵二叉树是否对称（为镜像二叉树）

1
2
3

   8       7
 6   6   7   7
5 7 7 5 7 7 7

A. 思路：

第一种情况：可以修改中序遍历，如果先访问left后访问right 和先访问right后访问left的结果一致，即为镜像树。
第二种情况：为了避免特殊情况，如全为同一个元素的非完全二叉树，可以在遍历时把空节点记录为None，以便比较序列时候可以对齐。

def isSymmetrical(rt: TreeNode):
    return isSymmetricalCore(rt, rt)

def isSymmetricalCore(rt1: TreeNode, rt2: TreeNode):
    if rt1 == rt2 == None:
        return True
    
    if rt1 == None or rt2 == None:
        return False
    
    if rt1.value != rt2.value:
        return False
    
    return isSymmetricalCore(rt1.left, rt2.right) and isSymmetricalCore(rt1.right, rt2.left)

Q. 顺时针打印矩阵

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

A. 思路：

打印一圈的条件为，从(starti, startj)->(starti, endj)->(endi, endj)->(endi, startj)
整体循环停止的条件为，开始坐标start超过了rows或cols的一半

def PrintMatrixClockwisely(numbers: list):
    if numbers == None or len(numbers) <= 0 or len(numbers[0]) <= 0:
        return

    rows = len(numbers)
    cols = len(numbers[0])

    start = 0
    while rows > 2*start and cols > 2*start:
        PrintMatrixInCircle(numbers, start, rows, cols)
        start += 1

def PrintMatrixInCircle(numbers: list, start: int, rows: int, cols: int):
    starti = start
    startj = start

    endi = rows-1-start
    endj = cols-1-start

    # 左上到右上
    for j in range(startj, endj+1):
        print(numbers[starti][j], end=' ')

    # 右上到右下
    for i in range(starti+1, endi+1):
        print(numbers[i][endj], end=' ')

    # 右下到左下
    for j in range(endj-1, startj-1, -1):
        print(numbers[endi][j], end=' ')

    # 左下到左上
    for i in range(endi-1, starti, -1):
        print(numbers[i][startj], end=' ')

Q. 定义min函数的栈：定义栈的数据结构，在该类型中实现一个能够找到栈的最小元素的min函数。在栈中调用min、push及pop的复杂度都是O(1)
A. 思路:

定义一个辅助栈SubStack，其栈顶存放最小值；
数据栈Stack存放逐次压入的数据；
每当Stack中压入的新数据dataNew比SubStack大时，Stack.push(dataNew)，SubStack.push(SubStack.top())，辅助栈拷贝栈顶，此时最小值仍为栈顶元素；
每当Stack中压入的新数据dataNew比SubStack小时，Stack.push(dataNew)，SubStack.push(dataNew)，辅助栈压入新元素，此时最小值为新元素；
1
2
3
3 4 2 1 pop 0
Stack 3 3,4 3,4,2 3,4,2,1 3,4,2 3,4,2,0
SubStack 3 3,3 3,3,2 3,3,2,1 3,3,2 3,3,2,0

Q. 栈的压入、弹出序列。输入两个整数序列，A={1,2,3,4,5}，B={4,5,3,2,1}是该压栈对应的一个弹出序列，但{4,3,5,1,2}就不可能是。
A. 思路：构建一个辅助栈，和pop序列抵消。

def IsPopOrder(push: list, pop: list):
    if push == None or pop == None or len(push) != len(pop):
        return

    subStack = []
    while len(push) != 0 or len(pop) != 0:
        # Push序列没空则压栈
        if len(push) != 0:
            pushNumber = push.pop(0)
            subStack.append(pushNumber)
        
        # Push序列已空，但是辅助栈和pop序列不匹配，则错误
        if pop[0] != subStack[-1] and len(push) == 0:
            return False
        
        # 辅助栈和pop序列匹配，相互抵消
        if pop[0] == subStack[-1]:
            subStack.pop(-1)
            pop.pop(0)
        
        # 三个序列全部为空，则全匹配成功
        if len(push) == 0 and len(pop) == 0 and len(subStack) == 0:
            return True

    return False

Q. 从上到下打印二叉树
A. bfs层次遍历

def PrintFromTopToBottom(rt: TreeNode):
    if rt == None:
        return

    rtQueue = []
    rtQueue.append(rt)
    while len(rtQueue) != 0:
        headRt = rtQueue.pop(0)
        print(headRt.value, end=' ')
        if headRt.left != None:
            rtQueue.append(headRt.left)
        if headRt.right != None:
            rtQueue.append(headRt.right)

Q. 分行打印二叉树，在层次遍历的基础上按行输出
A. 思路：

记录下一层待打印个数nextLevel
待打印变量toBePrinted记录本层还需打印多少个节点，当减为0时换行，然后将nextLevel赋给toBePrinted

def PrintFromTopToBottomWithLine(rt: TreeNode):
    if rt == None:
        return

    toBePrinted = 1
    nextLevel = 0
    rtQueue = []
    rtQueue.append(rt)
    while len(rtQueue) != 0:
        headRt = rtQueue.pop(0)
        print(headRt.value, end=' ')
        toBePrinted -= 1
        if headRt.left != None:
            nextLevel += 1
            rtQueue.append(headRt.left)
        if headRt.right != None:
            nextLevel += 1
            rtQueue.append(headRt.right)

        if toBePrinted == 0:
            print( )
            toBePrinted = nextLevel
            nextLevel = 0

Q. 二叉搜索树的后续遍历序列：输入一个整数数组，判断该数组是不是某二叉搜索树的后续遍历结果。

1 2	{5,7,6,9,11,10,8} -> True {7.4.6.5} -> False

A. 思路：

二叉搜索树：left < root < right
后续遍历序列的最后一个值肯定为根节点，由于搜索树的特性，比根节点小的为左子树序列，比根节点大的为右子树序列
如{5,7,6,9,11,10,8}：根节点8，则左子树为{5,7,6}<8，右子树为{9,11,10}>8

def VerifySquenceOfBST(sequence: list):
    if sequence == None or len(sequence) <= 0:
        return False

    length = len(sequence)
    root = sequence[-1]

    # 截取左子树
    leftIndex = 0
    while leftIndex < length - 1 and sequence[leftIndex] < root:
        leftIndex += 1

    rightIndex = leftIndex
    # 截取右子树
    while rightIndex < length - 1:
        if sequence[rightIndex] > root:
            rightIndex += 1
        else:
            return False

    leftFlag = True
    rightFlag = True
    # 有左子树
    if leftIndex > 0:
        leftFlag = VerifySquenceOfBST(sequence[:leftIndex])

    # 有右子树
    if leftIndex < length - 1:
        rightFlag = VerifySquenceOfBST(sequence[leftIndex: length-1]) # 注意递归序列中根节点已被去除

    return rightFlag & leftFlag

Q. 二叉树中和为某一值的路径：输入一棵二叉树和一个整数，打印出二叉树中所有节点值的和为输入整数的所有路径（从根节点开始向下知道叶节点所经过的节点形成一条路径）
A. 思路：

回溯法解决，nodeList存储已经走过的路径
在左右节点探索完后，直接nodeList中去除
遇到探索到叶节点时，打印路径

def PathOfSum(rt: TreeNode, nodeList: list, k: int):
    if rt == None:
        return

    nodeList.append(rt.value)
    if rt.left == None and rt.right == None:
        if sum(nodeList) == k:
            print(nodeList)
        return nodeList

    if rt.left != None:
        nodeList = PathOfSum(rt.left, nodeList, k)
        nodeList.pop(-1) # 探索后去掉

    if rt.right != None:
        nodeList = PathOfSum(rt.right, nodeList, k)
        nodeList.pop(-1) # 探索后去掉

    return nodeList

Q. 复杂链表的复制：复杂链表的结构包含

ListNode{
	int value; 			# 节点值
	ListNode next; 		# 指向下一个节点
	ListNode sibling;	# 指向任意节点
}

A -> B -> C -> D -> E
|____|____^    |    ^
     |_________|____|
     ^         |
     |_________|

A. 思路：

朴素思路：首先从头到尾复制链表，对每一个节点从头寻找其对应的sibling实现复制，O(n^2)
哈希思路：首先从头到尾复制链表，记录<N’, N>, <N, S>的两组映射，这样在复制链表N’中即可通过两组映射找到S并将其复制为S’，O(n)
原地复制：O(n)
- 从头到尾复制链表，将新复制得到的节点存放在原始节点之后，例如: A->A’->B->B’->C->C’->D->D’，pClone = ListNode(); pClone.value = A.value; pClone.next = A.next; pClone.sibling = None; A.next = pClone;
- 这样即可通过pClone.sibling = A.sibling.next实现sibling的复制;
- 最后从第二个节点出发，通过A.next = A.next.next截断即可。

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

    10
  6    14
4  8 12  16
-->
4<=>6<=>8<=>10<=>12<=>14<=>16

A. 思路：

中序遍历：对二叉搜索树进行中序遍历可以得到有序结果；
分治：当处理到根节点时，把树视成三部分：[leftList, root, rightList]，其中leftList和rightList看作已经排序好的链表，并且指针留在尾节点；
记录根节点root，再递归处理左子树convert(root.left, pLastNodeInList)，再处理根节点root.left = pLastNodeInList(左子树最后一个节点), pLastNodeInList.right = root ，再处理右子树convert(root.right, pLastNodeInList)

Q. 序列化二叉树：实现两个函数，分别用来序列化和反序列化二叉树
A. 思路：

序列化：用前序遍历序列化二叉树，遇到null节点在序列中赋值为特殊字符-1
反序列化：反序列化遇到-1时构建none节点，其余与先序遍历相似

# 序列化
def SerializeByPre(rt:TreeNode):
    if rt == None or rt.value == None:
        print('-1', end=' ')
        return 
    
    print(rt.value)
    if not rt.left:
        SerializeByPre(rt.left)
    if not rt.left:
        SerializeByPre(rt.right)

# 反序列化
def ConstructByPre(preorder: list):
    rt = TreeNode()
    return ConstructByPreCore(rt, preorder, 0)

def ConstructByPreCore(rt:TreeNode, preorder: list, index: int):
    if index >= len(preorder):
        return

    if preorder[index] == -1:
        index += 1
        return None, index

    # 先根
    rt = TreeNode()
    rt.value = preorder[index]
    index += 1

    # 再左
    rt.left, index = ConstructByPreCore(rt.left, preorder, index)
    # 再右
    rt.right, index = ConstructByPreCore(rt.right, preorder, index)

    return rt, index

Q. 字符串的排列：输入一个字符串，输出所有的排列。{a,b,c} -> {a,b,c; a,c,b; b,c,a; b,a,c; c,a,b; c,b,a}
A. 思路：回溯(三要素：候选、已选、访问标志)

def StrPermetuation(candidates: str):
    if candidates == None or len(candidates) <= 0:
        return

    visited = [False] * len(candidates)
    for i in range(len(candidates)):
        if not visited[i]:
            visited[i] = True
            StrPermetuationCore(candidates, candidates[i], visited)
            visited[i] = False

def StrPermetuationCore(candidates: str, permute: str, visited: list):
    if len(permute) == len(candidates):
        print(permute)
        return

    for i in range(len(candidates)):
        if not visited[i]:
            permute += candidates[i]
            visited[i] = True
            StrPermetuationCore(candidates, permute, visited)
            visited[i] = False

Q. （变体）字符串的组合：输入一个字符串，输出所有的组合。{a,b,c} -> {a,b,c,ab,ac,bc,abc}
A. 思路：回溯(三要素：候选、已选、访问标志)，这里的访问标志改为已选字符串长度

def StrCombinatorial(candidates: str):
    if candidates == None or len(candidates) <= 0:
        return

    visited = set()
    for i in range(len(candidates)):
        visited.add(candidates[i])
        StrCombinatorialCore(candidates, visited, i+1)
        visited.remove(candidates[i])

def StrCombinatorialCore(candidates: str, visited: set, index: int):
    print(visited)
    if index == len(candidates):
        return

    for i in range(index, len(candidates)):
        if candidates[i] not in visited:
            visited.add(candidates[i])
            StrCombinatorialCore(candidates, visited, index+1)
            visited.remove(candidates[i])

Q. （变体）输入一个含有8个数字的数组，判断有没有可能把这八个数字放在八个顶点，使得三组像对的面的四个顶点之和相同
A. 思路：展开全排列，在return时输出的判别条件为a1+a2+a3+a4=a5+a6+a7+a8, a1+a3+a5+a7=a2+a4+a6+a8, a1+a2+a5+a6=a3+a4+a7+a8

Q. （变体）八皇后
A. 思路：在判断是否访问时加入加入地图合法判断，即if visited[i][j] && check(map, visited, i, j)