Python 數(shù)據(jù)結(jié)構(gòu)面試必問(wèn)：棧、隊(duì)列、堆、二叉樹(shù)全手寫！（鏈表翻轉(zhuǎn)/堆排序吃香）
作者：Ss肥魚(yú)
面試 Python，數(shù)據(jù)結(jié)構(gòu)繞不過(guò)，尤其是鏈表翻轉(zhuǎn)、堆排序，基本是必問(wèn)。今天就一篇文章全搞定！
面試 Python，數(shù)據(jù)結(jié)構(gòu)繞不過(guò)！
尤其是鏈表翻轉(zhuǎn)、堆排序，基本是必問(wèn)。今天就一篇文章全搞定！
棧（Stack）—— 后進(jìn)先出（LIFO）
手寫實(shí)現(xiàn)：
class Stack:
def __init__(self):
self.items = []
def push(self, item):
"""入棧"""
self.items.append(item)
def pop(self):
"""出棧"""
if not self.is_empty():
return self.items.pop()
def peek(self):
"""查看棧頂元素"""
return self.items[-1] if not self.is_empty() else None
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# 測(cè)試
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop()) # 輸出 2隊(duì)列（Queue）—— 先進(jìn)先出（FIFO）
手寫實(shí)現(xiàn)：
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
"""入隊(duì)"""
self.items.append(item)
def dequeue(self):
"""出隊(duì)"""
if not self.is_empty():
return self.items.popleft()
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# 測(cè)試
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
print(queue.dequeue()) # 輸出 1鏈表翻轉(zhuǎn)（反轉(zhuǎn)鏈表）—— 高頻必問(wèn)！
單鏈表反轉(zhuǎn)：
class Node:
def __init__(self, val):
self.val = val
self.next = None
def reverse_linked_list(head):
prev = None
curr = head
while curr:
next_node = curr.next # 保存下一個(gè)節(jié)點(diǎn)
curr.next = prev # 反轉(zhuǎn)指針
prev = curr
curr = next_node
return prev # 新的頭節(jié)點(diǎn)
# 測(cè)試
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
new_head = reverse_linked_list(head)
while new_head:
print(new_head.val, end=' -> ')
new_head = new_head.next輸出：3 -> 2 -> 1 ->
堆排序（Heap Sort）—— 手撕算法題！
基本思路：
- 建最大堆
- 把堆頂元素放到數(shù)組末尾，重新堆化
手寫代碼：
def heapify(arr, n, i):
"""維護(hù)堆的性質(zhì)"""
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# 建堆
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 取堆頂元素，放到末尾
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # 堆頂與當(dāng)前末尾交換
heapify(arr, i, 0)
# 測(cè)試
arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print(arr) # [1, 3, 4, 5, 10]二叉樹(shù)（Binary Tree）—— 遍歷三板斧！
定義樹(shù)節(jié)點(diǎn)：
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None前序、中序、后序遍歷（遞歸版）：
def preorder(root):
if root:
print(root.val, end=' ')
preorder(root.left)
preorder(root.right)
def inorder(root):
if root:
inorder(root.left)
print(root.val, end=' ')
inorder(root.right)
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.val, end=' ')測(cè)試構(gòu)造一棵小樹(shù)：
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print("前序遍歷：")
preorder(root)
print("\n中序遍歷：")
inorder(root)
print("\n后序遍歷：")
postorder(root)小結(jié)
知識(shí)點(diǎn) | 備注 |
棧/隊(duì)列 | 必備基礎(chǔ)，手寫 |
鏈表翻轉(zhuǎn) | 頻繁面試題，記住三個(gè)指針 |
堆排序 | 必須熟悉堆化(heapify) |
二叉樹(shù)遍歷 | 遞歸套路要熟 |
責(zé)任編輯：趙寧寧
來(lái)源：
Ssoul肥魚(yú)
