数据结构学习笔记（3）——框架

2023-02-12

1. 数组遍历（线性迭代）

void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        // 迭代访问 arr[i]
    }
}

2. 链表遍历（线性迭代 + 非线性递归）

/* 基本的单链表节点 */
class ListNode {
    int val;
    ListNode next;
}

void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {
        // 迭代访问 p.val
    }
}

void traverse(ListNode head) {
    // 递归访问 head.val
    traverse(head.next);
}

3. 二叉树遍历框架（非线性递归）

/* 基本的二叉树节点 */
class TreeNode {
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
}

4. N 叉树遍历框架（非线性递归）

单链表就是一个节点只能连一个节点，二叉树可以理解为单链表的扩展（1 对 2），所以 N 叉树也可以理解为单链表的扩展（1 对多）。

/* 基本的 N 叉树节点 */
class TreeNode {
    int val;
    TreeNode[] children;
}

void traverse(TreeNode root) {
    for (TreeNode child : root.children)
        traverse(child);
}

5. 图的遍历框架（非线性递归）

图是好几个 N 叉树的结合体，所以 N 叉树的遍历可以扩展为图的遍历。

假如要检查环，就用 boolean 数组 visited 来做标记。

6. 二分搜索

二分搜索是双指针技巧的运用。


int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}