LeetCode 数据结构与算法

链表

快慢指针的思想

一个走一步，一个走两步，相遇时，慢的

树

DFS：一条路走到黑（深度优先）
BFS：一层一层走（广度优先）

按层：BFS

把每一层放进队列中，先进先出

from collections import deque

def bfs(root):
    if not root:
        return []

    queue = deque([root])

    while queue:
        size = len(queue)

        for _ in range(size):
            node = queue.popleft()

            # 处理当前节点

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

路径与子数信息：DFS

递归：自顶向下或者自顶向上

自顶向下

把状态或者信息向下传

def dfs(node, 状态参数):
    if not node:
        return

    # 处理当前节点
    do_something(node, 状态参数)

    dfs(node.left, 更新后的状态)
    dfs(node.right, 更新后的状态)

自底向上

子树算完，把结果“返回上来”

def dfs(node):
    if not node:
        return base_value

    left = dfs(node.left)
    right = dfs(node.right)

    # 利用左右子树结果计算当前
    return combine(left, right, node)

所有路径与组合：回溯

def backtrack(node, path):
    if not node:
        return

    path.append(node.val)

    # 终止条件
    if 满足条件:
        res.append(path[:])

    backtrack(node.left, path)
    backtrack(node.right, path)

    path.pop()  # 撤销

BST

中序模版

def inorder(node):
    if not node:
        return

    inorder(node.left)

    # 处理 node

    inorder(node.right)