算法 Algorithm • 中

前言

本读书笔记节选自krahets大佬编写的《Hello 算法》。勉励自己开始系统的算法学习。

7. 树

7.1 二叉树

「二叉树 binary tree」是一种非线性数据结构，代表着祖先与后代之间的派生关系，体现着“一分为二”的分治逻辑。二叉树的基本单元是节点，每个节点包含值、左子节点引用、右子节点引用。

/* 二叉树节点类 */
class TreeNode {
    int val;         // 节点值
    TreeNode left;   // 左子节点引用
    TreeNode right;  // 右子节点引用
    TreeNode(int x) { val = x; }
}

每个节点都有两个引用。当给定一个二叉树的节点时，该节点的左子节点及其以下节点形成的树称为该节点的「左子树 left subtree」，同理可得「右子树 right subtree」。

在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树。

二叉树常见术语

二叉树的常用术语如下面所示。

根节点 root node：位于二叉树顶层的节点，没有父节点。
叶节点 leaf node：没有子节点的节点，其两个指针均指向None。
边 edge：连接两个节点的线段，即节点引用（left，right）。
节点所在的层 level：从顶至底递增，根节点所在层为1。
节点的度 degree：节点的子节点的数量。在二叉树中，度的取值范围是0、1、2。
二叉树的高度 height：从根节点到最远叶节点所经过的边的数量。
节点的深度 depth：从根节点到该节点所经过的边的数量。
节点的高度 height：从最远叶节点到该节点所经过的边的数量。

注意，我们通常将“高度”和“深度”定义为“走过边的数量”，但有些题目或教材可能会将其定义为“走过节点的数量”。在这种情况下，高度和深度都需要加1。

二叉树常见问题

（1）二叉树某节点所在的深度（层数）

在递归方案中，从根节点开始，如果当前节点是目标节点，返回当前的深度。否则，递归地搜索该节点的左右子节点，同时深度加一。如果在左或右子树中找到了目标节点，返回找到的深度。

int findLevel(TreeNode root, int targetVal, int level) {
    if(root == null) {
        return 0;
    }

    if(root.val == targetVal) {
        return level;
    }

    int leftLevel = findLevel(root.left, targetVal, level + 1);
    if(leftLevel != 0) {
        return leftLevel;
    }

    return findLevel(root.right, targetVal, level + 1);
}

int level = findLevel(root, targetVal, 1);

除了递归遍历法，还可以通过迭代的方式进行层次遍历（广度优先搜索，BFS）来找到节点的深度。

int findLevelBFS(TreeNode root, int targetVal) {
    if(root == null) {
        return 0;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    Queue<Integer> levels = new LinkedList<>();
    queue.add(root);
    levels.add(1);

    while(!queue.isEmpty()) {
        TreeNode currentNode = queue.poll();
        int currentLevel = levels.poll();

        if(currentNode.val == targetVal) {
            return currentLevel;
        }

        if(currentNode.left != null) {
            queue.add(currentNode.left);
            levels.add(currentLevel + 1);
        }

        if(currentNode.right != null) {
            queue.add(currentNode.right);
            levels.add(currentLevel + 1);
        }
    }

    return 0;
}

（2）二叉树的节点总数 | 边总数

二叉树的节点总数等于根节点加上左子树的节点总数和右子树的节点总数。

int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return 1 + countNodes(root.left) + countNodes(root.right);
}

除了递归，还可以通过迭代的方式来计算节点总数，通常使用层次遍历。

int countNodesIterative(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int count = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        TreeNode currentNode = queue.poll();
        count++;

        if (currentNode.left != null) {
            queue.add(currentNode.left);
        }

        if (currentNode.right != null) {
            queue.add(currentNode.right);
        }
    }

    return count;
}

对于边总数，一个包含N个节点的非空二叉树，其边数E为E = N − 1。

（3）二叉树的高度 | 某节点高度

二叉树的高度是从根节点到最远叶子节点的最长路径上的节点数。可以使用递归方法从根节点开始，递归地计算左子树和右子树的高度，然后取两者中的较大值，并加上1（根节点自身）。

int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);
    return Math.max(leftHeight, rightHeight) + 1;
}

使用迭代的方法来计算二叉树的高度通常涉及层次遍历，下面是实现方法。

int getHeightIterative(TreeNode root) {
    if (root == null) {
        return 0;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    int height = 0;

    while (!queue.isEmpty()) {
        int levelSize = queue.size(); // 当前层的节点数量

        // 遍历当前层的所有节点
        for (int i = 0; i < levelSize; i++) {
            TreeNode current = queue.poll(); // 从队列中移除节点

            // 将子节点加入队列
            if (current.left != null) {
                queue.offer(current.left);
            }
            if (current.right != null) {
                queue.offer(current.right);
            }
        }

        // 完成一层的遍历，高度加 1
        height++;
    }

    return height;
}

（4）二叉树的子叶总数

在递归方法中，从根节点开始遍历。如果遇到一个null节点，返回0。如果遇到一个叶子节点，返回1。然后，递归地计算左子树和右子树的叶子节点数，并将它们相加以得到总数。

int countLeaves(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if (root.left == null && root.right == null) {
        return 1; // 是一个叶子节点
    }
    return countLeaves(root.left) + countLeaves(root.right);
}

使用迭代的方法来计算二叉树的子叶总数涉及层次遍历，下面是实现方法。

int countLeavesIterative(TreeNode root) {
    if (root == null) {
        return 0;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    int leafCount = 0;

    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();

        if (current.left == null && current.right == null) {
            leafCount++; // 是一个叶子节点
        }

        if (current.left != null) {
            queue.offer(current.left);
        }

        if (current.right != null) {
            queue.offer(current.right);
        }
    }

    return leafCount;
}

多叉树（扩展）

多叉树（也称为多路树或K叉树）是一种树形数据结构，其中每个节点可以有多于两个子节点。这与二叉树形成对比，在二叉树中，每个节点最多只能有两个子节点。

class TreeNode {
    int val;
    List<TreeNode> children;
    TreeNode(int x) {
        val = x;
        children = new ArrayList<>();
    }
}

（1）多叉树某节点所在的深度（层数）

在多叉树中，一个节点的深度是从根节点到该节点的唯一路径上的边的数量。根节点的深度为0，其直接子节点的深度为1，依此类推。

// 递归写法
int findDepth(TreeNode root, int target, int depth) {
    if (root == null) {
        return -1; // 节点未找到
    }

    if (root.val == target) {
        return depth; // 节点找到，返回深度
    }

    for (TreeNode child : root.children) {
        int result = findDepth(child, target, depth + 1);
        if (result != -1) { // 如果在子树中找到节点，返回结果
            return result;
        }
    }

    return -1; // 在这个子树中没有找到节点
}

// 迭代写法
int findNodeDepthIterative(TreeNode root, int target) {
    if (root == null) {
        return -1;
    }

    Queue<TreeNode> nodeQueue = new LinkedList<>();
    Queue<Integer> depthQueue = new LinkedList<>();

    nodeQueue.offer(root);
    depthQueue.offer(0);  // 根节点的深度是0

    while (!nodeQueue.isEmpty()) {
        TreeNode currentNode = nodeQueue.poll();
        int currentDepth = depthQueue.poll();

        // 如果找到了目标节点
        if (currentNode.val == target) {
            return currentDepth;
        }

        // 将子节点加入队列
        for (TreeNode child : currentNode.children) {
            nodeQueue.offer(child);
            depthQueue.offer(currentDepth + 1);  // 子节点的深度是当前节点深度+1
        }
    }

    return -1;  // 如果未找到目标节点
}

（2）多叉树的节点总数

多叉树的节点总数等于根节点自身（1个节点）加上所有子树的节点总数。

// 递归写法
int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int count = 1; // 计算根节点
    for (TreeNode child : root.children) {
        count += countNodes(child); // 递归计算每个子树的节点数，并累加
    }

    return count;
}

// 迭代写法
int countNodesIterative(TreeNode root) {
    if (root == null) {
        return 0;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    int count = 0;
    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();
        count++; // 计算当前节点

        for (TreeNode child : current.children) {
            queue.offer(child); // 将子节点加入队列，以便后续遍历
        }
    }

    return count;
}

（3）多叉树的高度 | 某节点高度

在递归方案中，从根节点开始，递归地计算所有子树的高度，取其中的最大值，并加1（包括当前节点自己）。若遇到空节点，返回0。

// 递归写法
int height(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int maxHeight = 0;
    for (TreeNode child : root.children) {
        maxHeight = Math.max(maxHeight, height(child));
    }

    return 1 + maxHeight;
}

// 迭代写法
int findHeightIterative(TreeNode root) {
    if (root == null) {
        return 0;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    int height = 0;

    while (!queue.isEmpty()) {
        int levelSize = queue.size(); // 当前层的节点数
        for (int i = 0; i < levelSize; i++) {
            TreeNode current = queue.poll();

            for (TreeNode child : current.children) {
                queue.offer(child);  // 将子节点加入队列，以便后续遍历
            }
        }

        height++;  // 完成一层的遍历后，高度加1
    }

    return height;
}

（4）多叉树的子叶总数

在递归方案中，从根节点开始，递归地遍历每个子树。如果一个节点没有子节点，则它是一个叶子节点，计数器加一。递归结束后，计数器的值即为叶子节点的总数。

// 递归写法
int countLeaves(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if (root.children.isEmpty()) {
        return 1; // 是一个叶子节点
    }

    int count = 0;
    for (TreeNode child : root.children) {
        count += countLeaves(child);
    }
    return count;
}

// 迭代写法
int countLeafNodesIterative(TreeNode root) {
    if (root == null) {
        return 0;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    int leafCount = 0;

    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();

        // 如果是叶子节点
        if (current.children.isEmpty()) {
            leafCount++;
        }

        // 将子节点加入队列
        for (TreeNode child : current.children) {
            queue.offer(child);
        }
    }

    return leafCount;
}

二叉树基本操作

（1）初始化二叉树

与链表类似，首先初始化节点，然后构建引用（指针）。

// 初始化节点
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
// 构建引用指向（即指针）
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

（2）插入与删除节点

与链表类似，在二叉树中插入与删除节点可以通过修改指针来实现。下图给出了一个示例。

TreeNode P = new TreeNode(0);
// 在 n1 -> n2 中间插入节点 P
n1.left = P;
P.left = n2;
// 删除节点 P
n1.left = n2;

需要注意的是，插入节点可能会改变二叉树的原有逻辑结构，而删除节点通常意味着删除该节点及其所有子树。因此，在二叉树中，插入与删除操作通常是由一套操作配合完成的，以实现有实际意义的操作。

常见二叉树类型

完美二叉树

「完美二叉树 perfect binary tree」除了最底层外，其余所有层的节点都被完全填满。在完美二叉树中，叶节点的度为0，其余所有节点的度都为2。若树高度为h，则节点总数为2^(h + 1) - 1，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象。

完全二叉树

「完全二叉树 complete binary tree」只有最底层的节点未被填满，且最底层节点尽量靠左填充。

完满二叉树

「完满二叉树 full binary tree」除了叶节点之外，其余所有节点都有两个子节点。

平衡二叉树

「平衡二叉树 balanced binary tree」中任意节点的左子树和右子树高度之差的绝对值不超过1。

二叉树的退化

当二叉树的每层节点都被填满时，达到“完美二叉树”。完美二叉树是理想情况，可以充分发挥二叉树“分治”的优势。而当所有节点都偏向一侧时，二叉树就会退化为“链表”，各项操作都变为线性操作，时间复杂度退化至O(n)。

如下表所示，在最佳和最差结构下，二叉树的叶节点数量、节点总数、高度等达到极大或极小值。

	完美二叉树	链表
第`i`层的节点数量	`2^(i - 1)`	`1`
高度`h`树的叶节点数量	`2^h`	`1`
高度`h`树的节点总数	`2^(h + 1) - 1`	`h + 1`
节点总数`n`树的高度	`log2(n + 1) - 1`	`n + 1`

7.2 二叉树遍历

二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。

层序遍历

如下图所示，「层序遍历 level-order traversal」从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。

层序遍历本质上属于「广度优先遍历 breadth-first traversal」，它体现了一种“一圈一圈向外扩展”的逐层遍历方式。

广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则，而广度优先遍历则遵循“逐层推进”的规则，两者背后的思想是一致的。

/* 层序遍历 */
List<Integer> levelOrder(TreeNode root) {
    // 初始化队列，加入根节点
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    // 初始化一个列表，用于保存遍历序列
    List<Integer> list = new ArrayList<>();
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // 队列出队
        list.add(node.val);           // 保存节点值
        if (node.left != null)
            queue.offer(node.left);   // 左子节点入队
        if (node.right != null)
            queue.offer(node.right);  // 右子节点入队
    }
    return list;
}

时间复杂度：所有节点被访问一次，使用O(n)时间，其中n为节点数量。
空间复杂度：在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在(n + 1) / 2个节点，占用O(n)空间。

前序、中序、后序遍历

相应地，前序、中序和后序遍历都属于「深度优先遍历 depth-first traversal」，它体现了一种“先走到尽头，再回溯继续”的遍历方式。

下图展示了对二叉树进行深度优先遍历的工作原理。深度优先遍历就像是绕着整个二叉树的外围“走”一圈，在每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后序遍历。

深度优先搜索通常基于递归实现。

/* 前序遍历 */
void preOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：根节点 -> 左子树 -> 右子树
    list.add(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

/* 中序遍历 */
void inOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：左子树 -> 根节点 -> 右子树
    inOrder(root.left);
    list.add(root.val);
    inOrder(root.right);
}

/* 后序遍历 */
void postOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：左子树 -> 右子树 -> 根节点
    postOrder(root.left);
    postOrder(root.right);
    list.add(root.val);
}

下图展示了前序遍历二叉树的递归过程，其可分为“递”和“归”两个逆向的部分。

“递”表示开启新方法，程序在此过程中访问下一个节点。
“归”表示函数返回，代表当前节点已经访问完毕。

时间复杂度：所有节点被访问一次，使用O(n)时间，其中n为节点数量。
空间复杂度：在最差情况下，即树退化为链表时，递归深度达到n，系统占用O(n)栈帧空间。

7.3 二叉树数组表示

在链表表示下，二叉树的存储单元为节点TreeNode，节点之间通过指针相连接。那么，能否用数组来表示二叉树呢？答案是肯定的。

表示完美二叉树

给定一个完美二叉树，将所有节点按照层序遍历的顺序存储在一个数组中，则每个节点都对应唯一的数组索引。

根据层序遍历的特性，可以推导出父节点索引与子节点索引之间的“映射公式”。若节点的索引为i，则该节点的左子节点索引为2i + 1，右子节点索引为2i + 2。

表示任意二叉树

完美二叉树是一个特例，在二叉树的中间层通常存在许多None。由于层序遍历序列并不包含这些None，因此无法仅凭该序列来推测None的数量和分布位置。这意味着存在多种二叉树结构都符合该层序遍历序列。

为了解决此问题，可以考虑在层序遍历序列中显式地写出所有None。如下图所示，这样处理后，层序遍历序列就可以唯一表示二叉树了。

/* 二叉树的数组表示 */
// 使用 int 的包装类 Integer ，就可以使用 null 来标记空位
Integer[] tree = { 1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, 15 };

表示完全二叉树

完全二叉树非常适合使用数组来表示。根据完全二叉树的定义，None只出现在最底层且靠右的位置，因此所有None一定出现在层序遍历序列的末尾。这意味着使用数组表示完全二叉树时，可以省略存储所有None，非常方便。

以下代码实现了一个基于数组表示的二叉树，包括以下几种操作。

给定某节点，获取它的值、左（右）子节点、父节点。
获取前序遍历、中序遍历、后序遍历、层序遍历序列。

/* 数组表示下的二叉树类 */
class ArrayBinaryTree {
    private List<Integer> tree;

    /* 构造方法 */
    public ArrayBinaryTree(List<Integer> arr) {
        tree = new ArrayList<>(arr);
    }

    /* 节点数量 */
    public int size() {
        return tree.size();
    }

    /* 获取索引为 i 节点的值 */
    public Integer val(int i) {
        // 若索引越界，则返回 null ，代表空位
        if (i < 0 || i >= size())
            return null;
        return tree.get(i);
    }

    /* 获取索引为 i 节点的左子节点的索引 */
    public Integer left(int i) {
        return 2 * i + 1;
    }

    /* 获取索引为 i 节点的右子节点的索引 */
    public Integer right(int i) {
        return 2 * i + 2;
    }

    /* 获取索引为 i 节点的父节点的索引 */
    public Integer parent(int i) {
        return (i - 1) / 2;
    }

    /* 层序遍历 */
    public List<Integer> levelOrder() {
        List<Integer> res = new ArrayList<>();
        // 直接遍历数组
        for (int i = 0; i < size(); i++) {
            if (val(i) != null)
                res.add(val(i));
        }
        return res;
    }

    /* 深度优先遍历 */
    private void dfs(Integer i, String order, List<Integer> res) {
        // 若为空位，则返回
        if (val(i) == null)
            return;
        // 前序遍历
        if (order == "pre")
            res.add(val(i));
        dfs(left(i), order, res);
        // 中序遍历
        if (order == "in")
            res.add(val(i));
        dfs(right(i), order, res);
        // 后序遍历
        if (order == "post")
            res.add(val(i));
    }

    /* 前序遍历 */
    public List<Integer> preOrder() {
        List<Integer> res = new ArrayList<>();
        dfs(0, "pre", res);
        return res;
    }

    /* 中序遍历 */
    public List<Integer> inOrder() {
        List<Integer> res = new ArrayList<>();
        dfs(0, "in", res);
        return res;
    }

    /* 后序遍历 */
    public List<Integer> postOrder() {
        List<Integer> res = new ArrayList<>();
        dfs(0, "post", res);
        return res;
    }
}

7.4 二叉搜索树

「二叉搜索树 binary search tree」满足以下条件。

对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值。
任意节点的左、右子树也是二叉搜索树，即同样满足上面条件。

二叉搜索树的操作

将二叉搜索树封装为一个类ArrayBinaryTree，并声明一个成员变量root，指向树的根节点。

（1）查找节点

给定目标节点值num，可以根据二叉搜索树的性质来查找。如下图所示，声明一个节点cur，从二叉树的根节点root出发，循环比较节点值cur.val和num之间的大小关系。

若cur.val < num，说明目标节点在cur的右子树中，因此执行cur = cur.right。
若cur.val > num，说明目标节点在cur的左子树中，因此执行cur = cur.left。
若cur.val = num，说明找到目标节点，跳出循环并返回该节点。

二叉搜索树的查找操作与二分查找算法的工作原理一致，都是每轮排除一半情况。循环次数最多为二叉树的高度，当二叉树平衡时，使用O(logn)时间。

/* 查找节点 */
TreeNode search(int num) {
    TreeNode cur = root;
    // 循环查找，越过叶节点后跳出
    while (cur != null) {
        // 目标节点在 cur 的右子树中
        if (cur.val < num)
            cur = cur.right;
        // 目标节点在 cur 的左子树中
        else if (cur.val > num)
            cur = cur.left;
        // 找到目标节点，跳出循环
        else
            break;
    }
    // 返回目标节点
    return cur;
}

（2）插入节点

给定一个待插入元素num，根据二叉搜索树“左子树 < 根节点 < 右子树”的性质，插入流程如下。

查找插入位置：与查找操作相似，从根节点出发，根据当前节点值和num的大小关系循环向下搜索，直到越过叶节点（遍历至None）时跳出循环。
在该位置插入节点：初始化节点num，将该节点置于None的位置。

在代码实现中，需要注意以下两点。

二叉搜索树不允许存在重复节点，否则将违反其定义。因此，若待插入节点在树中已存在，则不执行插入，直接返回。
为了实现插入节点，需要借助节点pre保存上一轮循环的节点。这样在遍历至None时，可以获取到其父节点，从而完成节点插入操作。

/* 插入节点 */
void insert(int num) {
    // 若树为空，则初始化根节点
    if (root == null) {
        root = new TreeNode(num);
        return;
    }
    TreeNode cur = root, pre = null;
    // 循环查找，越过叶节点后跳出
    while (cur != null) {
        // 找到重复节点，直接返回
        if (cur.val == num)
            return;
        pre = cur;
        // 插入位置在 cur 的右子树中
        if (cur.val < num)
            cur = cur.right;
        // 插入位置在 cur 的左子树中
        else
            cur = cur.left;
    }
    // 插入节点
    TreeNode node = new TreeNode(num);
    if (pre.val < num)
        pre.right = node;
    else
        pre.left = node;
}

与查找节点相同，插入节点使用O(logn)时间。

（3）删除节点

先在二叉树中查找到目标节点，再将其从二叉树中删除。与插入节点类似，需要保证在删除操作完成后，二叉搜索树的“左子树 < 根节点 < 右子树”的性质仍然满足。

因此，需要根据目标节点的子节点数量，共分为0、1和2这三种情况，执行对应的删除节点操作。

当待删除节点的度为0时，表示该节点是叶节点，可以直接删除。

当待删除节点的度为1时，将待删除节点替换为其子节点即可。

当待删除节点的度为2时，无法直接删除它，而需要使用一个节点替换该节点。由于要保持二叉搜索树“左 < 根 < 右”的性质，因此这个节点可以是右子树的最小节点或左子树的最大节点。

假设选择右子树的最小节点，即中序遍历的下一个节点，删除操作流程下图所示。

找到待删除节点在“中序遍历序列”中的下一个节点，记为tmp。
将tmp的值覆盖待删除节点的值，并在树中递归删除节点tmp。

实际上，右子树的最小值和左子树的最大值都可以通过中序遍历来找。只需要找到给定节点在该序列中的位置，然后查看它的前一个（左子树最大）或后一个节点（右子树最小）即可。原因是二叉搜索树中序遍历有序。

删除节点操作同样使用O(logn)时间，其中查找待删除节点需要O(logn)时间，获取中序遍历后继节点需要O(logn)时间。

/* 删除节点 */
void remove(int num) {
    // 若树为空，直接提前返回
    if (root == null)
        return;
    TreeNode cur = root, pre = null;
    // 循环查找，越过叶节点后跳出
    while (cur != null) {
        // 找到待删除节点，跳出循环
        if (cur.val == num)
            break;
        pre = cur;
        // 待删除节点在 cur 的右子树中
        if (cur.val < num)
            cur = cur.right;
        // 待删除节点在 cur 的左子树中
        else
            cur = cur.left;
    }
    // 若无待删除节点，则直接返回
    if (cur == null)
        return;
    // 子节点数量 = 0 or 1
    if (cur.left == null || cur.right == null) {
        // 当子节点数量 = 0 / 1 时， child = null / 该子节点
        TreeNode child = cur.left != null ? cur.left : cur.right;
        // 删除节点 cur
        if (cur != root) {
            if (pre.left == cur)
                pre.left = child;
            else
                pre.right = child;
        } else {
            // 若删除节点为根节点，则重新指定根节点
            root = child;
        }
    }
    // 子节点数量 = 2
    else {
        // 获取中序遍历中 cur 的下一个节点
        TreeNode tmp = cur.right;
        while (tmp.left != null) {
            tmp = tmp.left;
        }
        // 递归删除节点 tmp
        remove(tmp.val);
        // 用 tmp 覆盖 cur
        cur.val = tmp.val;
    }
}

中序遍历有序

二叉树的中序遍历遵循“左 -> 根 -> 右”的遍历顺序，而二叉搜索树满足“左子节点 < 根节点 < 右子节点”的大小关系。

这意味着在二叉搜索树中进行中序遍历时，总是会优先遍历下一个最小节点，从而得出一个重要性质，二叉搜索树的中序遍历序列是升序的。

利用中序遍历升序的性质，我们在二叉搜索树中获取有序数据仅需O(n)时间，无须进行额外的排序操作，非常高效。

二叉搜索树的效率

给定一组数据，可以考虑使用数组或二叉搜索树存储。二叉搜索树的各项操作的时间复杂度都是对数阶，具有稳定且高效的性能表现。只有在高频添加、低频查找删除的数据适用场景下，数组比二叉搜索树的效率更高。

	无序数组	二叉搜索树
查找元素	`O(n)`	`O(logn)`
插入元素	`O(1)`	`O(logn)`
删除元素	`O(n)`	`O(logn)`

在理想情况下，二叉搜索树是“平衡”的，这样就可以在logn轮循环内查找任意节点。

然而，如果在二叉搜索树中不断地插入和删除节点，可能导致二叉树退化为链表，这时各种操作的时间复杂度也会退化为O(n)。

7.5 AVL 树

在二叉搜索树章节中，提到了在多次插入和删除操作后，二叉搜索树可能退化为链表。这种情况下，所有操作的时间复杂度将从O(logn)恶化为O(n)。

与二叉搜索树不同，AVL树不会退化，各种操作的时间复杂度保持在O(logn)级别。换句话说，在需要频繁进行增删查改操作的场景中，AVL树能始终保持高效的数据操作性能，具有很好的应用价值。

AVL 树常见术语

AVL树既是二叉搜索树也是平衡二叉树，同时满足这两类二叉树的所有性质，因此也被称为「平衡二叉搜索树 balanced binary search tree」。

（1）节点高度

由于AVL树的相关操作需要获取节点高度，因此需要为节点类添加height变量。

/* AVL 树节点类 */
class TreeNode {
    public int val;        // 节点值
    public int height;     // 节点高度
    public TreeNode left;  // 左子节点
    public TreeNode right; // 右子节点
    public TreeNode(int x) { val = x; }
}

“节点高度”是指从该节点到最远叶节点的距离，即所经过的“边”的数量。需要特别注意的是，叶节点的高度为0，而空节点的高度为-1。下面创建两个工具函数，分别用于获取和更新节点的高度。

/* 获取节点高度 */
int height(TreeNode node) {
    // 空节点高度为 -1 ，叶节点高度为 0
    return node == null ? -1 : node.height;
}

/* 更新节点高度 */
void updateHeight(TreeNode node) {
    // 节点高度等于最高子树高度 + 1
    node.height = Math.max(height(node.left), height(node.right)) + 1;
}

（2）节点平衡因子

节点的「平衡因子 balance factor」定义为节点左子树的高度减去右子树的高度，同时规定空节点的平衡因子为0。同样将获取节点平衡因子的功能封装成函数，方便后续使用。

/* 获取平衡因子 */
int balanceFactor(TreeNode node) {
    // 空节点平衡因子为 0
    if (node == null)
        return 0;
    // 节点平衡因子 = 左子树高度 - 右子树高度
    return height(node.left) - height(node.right);
}

设平衡因子为f，则一棵AVL树的任意节点的平衡因子皆满足-1 <= f <= 1。

AVL 树旋转

AVL树的特点在于“旋转”操作，它能够在不影响二叉树的中序遍历序列的前提下，使失衡节点重新恢复平衡。换句话说，旋转操作既能保持“二叉搜索树”的性质，也能使树重新变为“平衡二叉树”。

规定，平衡因子绝对值> 1的节点称为“失衡节点”。根据节点失衡情况的不同，旋转操作分为四种，右旋、左旋、先右旋后左旋、先左旋后右旋。下面将详细介绍这些旋转操作。

（1）右旋

如下图所示，节点下方为平衡因子。从底至顶看，二叉树中首个失衡节点是“节点 3”（左子树高度减右子树高度）。找出以该失衡节点为根节点的子树，将该节点记为node，其左子节点记为child，执行“右旋”操作。完成右旋后，子树已经恢复平衡，并且仍然保持二叉搜索树的特性。

注意，当节点child有右子节点（记为grandChild）时，需要在右旋中添加一步，将grandChild作为node的左子节点。

“向右旋转”是一种形象化的说法，实际上需要通过修改节点指针来实现，代码如下所示。

/* 右旋操作 */
TreeNode rightRotate(TreeNode node) {
    TreeNode child = node.left;
    TreeNode grandChild = child.right;
    // 以 child 为原点，将 node 向右旋转
    child.right = node;
    node.left = grandChild;
    // 更新节点高度
    updateHeight(node);
    updateHeight(child);
    // 返回旋转后子树的根节点
    return child;
}

（2）左旋

相应的，如果考虑上述失衡二叉树的“镜像”，则需要执行下图所示的“左旋”操作。

同理，当节点child有左子节点（记为grandChild）时，需要在左旋中添加一步，将grandChild作为node的右子节点。

实际上，右旋和左旋操作在逻辑上是镜像对称的，它们分别解决的两种失衡情况也是对称的。基于对称性，只需将右旋的实现代码中的所有的left替换为right，将所有的right替换为left，即可得到左旋的实现代码。

/* 左旋操作 */
TreeNode leftRotate(TreeNode node) {
    TreeNode child = node.right;
    TreeNode grandChild = child.left;
    // 以 child 为原点，将 node 向左旋转
    child.left = node;
    node.right = grandChild;
    // 更新节点高度
    updateHeight(node);
    updateHeight(child);
    // 返回旋转后子树的根节点
    return child;
}

（3）先左旋后右旋

对于下图中的失衡节点3，仅使用左旋或右旋都无法使子树恢复平衡。此时需要先对child执行“左旋”，再对node执行“右旋”。

（4）先右旋后左旋

对于上述失衡二叉树的镜像情况，需要先对child执行“右旋”，然后对node执行“左旋”。

（5）旋转的选择

下面展示的四种失衡情况，分别需要采用右旋、左旋、先右后左、先左后右的旋转操作。

如下表所示，通过判断失衡节点的平衡因子以及较高一侧子节点的平衡因子的正负号，来确定失衡节点属于哪种情况。

失衡节点的平衡因子	子节点的平衡因子	应采用的旋转方法
`> 1` 即左偏树	`>= 0`	右旋
`> 1` 即左偏树	`< 0`	先左旋后右旋
`< -1` 即右偏树	`<= 0`	左旋
`< -1` 即右偏树	`> 0`	先右旋后左旋

为了便于使用，可以将旋转操作封装成一个函数。有了这个函数，就能对各种失衡情况进行旋转，使失衡节点重新恢复平衡。

/* 执行旋转操作，使该子树重新恢复平衡 */
TreeNode rotate(TreeNode node) {
    // 获取节点 node 的平衡因子
    int balanceFactor = balanceFactor(node);
    // 左偏树
    if (balanceFactor > 1) {
        if (balanceFactor(node.left) >= 0) {
            // 右旋
            return rightRotate(node);
        } else {
            // 先左旋后右旋
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
    }
    // 右偏树
    if (balanceFactor < -1) {
        if (balanceFactor(node.right) <= 0) {
            // 左旋
            return leftRotate(node);
        } else {
            // 先右旋后左旋
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
    }
    // 平衡树，无须旋转，直接返回
    return node;
}

AVL 树常用操作

（1）插入节点

AVL树的节点插入操作与二叉搜索树在主体上类似。唯一的区别在于，在AVL树中插入节点后，从该节点到根节点的路径上可能会出现一系列失衡节点。因此，需要从这个节点开始，自底向上执行旋转操作，使所有失衡节点恢复平衡。

/* 插入节点 */
void insert(int val) {
    root = insertHelper(root, val);
}

/* 递归插入节点（辅助方法） */
TreeNode insertHelper(TreeNode node, int val) {
    if (node == null)
        return new TreeNode(val);
    /* 1. 查找插入位置，并插入节点 */
    if (val < node.val)
        node.left = insertHelper(node.left, val);
    else if (val > node.val)
        node.right = insertHelper(node.right, val);
    else
        return node; // 重复节点不插入，直接返回
    updateHeight(node); // 更新节点高度
    /* 2. 执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);
    // 返回子树的根节点
    return node;
}

（2）删除节点

在二叉搜索树的删除节点方法的基础上，需要从底至顶地执行旋转操作，使所有失衡节点恢复平衡。

/* 删除节点 */
void remove(int val) {
    root = removeHelper(root, val);
}

/* 递归删除节点（辅助方法） */
TreeNode removeHelper(TreeNode node, int val) {
    if (node == null)
        return null;
    /* 1. 查找节点，并删除之 */
    if (val < node.val)
        node.left = removeHelper(node.left, val);
    else if (val > node.val)
        node.right = removeHelper(node.right, val);
    else {
        if (node.left == null || node.right == null) {
            TreeNode child = node.left != null ? node.left : node.right;
            // 子节点数量 = 0 ，直接删除 node 并返回
            if (child == null)
                return null;
            // 子节点数量 = 1 ，直接删除 node
            else
                node = child;
        } else {
            // 子节点数量 = 2 ，则将中序遍历的下个节点删除，并用该节点替换当前节点
            TreeNode temp = node.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            node.right = removeHelper(node.right, temp.val);
            node.val = temp.val;
        }
    }
    updateHeight(node); // 更新节点高度
    /* 2. 执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);
    // 返回子树的根节点
    return node;
}

（3）查找节点

AVL树的节点查找操作与二叉搜索树一致，在此不再赘述。

8. 堆

8.1 堆

「堆 heap」是一种满足特定条件的完全二叉树，主要分为两种类型。

「大顶堆 max heap」：任意节点的值>=其子节点的值。
「小顶堆 min heap」：任意节点的值<=其子节点的值。

堆作为完全二叉树的一个特例，具有以下特性。

最底层节点靠左填充，其他层的节点都被填满。
二叉树的根节点称为“堆顶”，底层最靠右的节点称为“堆底”。
对于大顶堆（小顶堆），堆顶元素（即根节点）的值分别是最大（最小）的。

堆常用操作

堆通常用作实现优先队列，可以将“优先队列”和“堆”看作等价的数据结构。许多编程语言提供的是「优先队列 priority queue」，这是一种抽象数据结构，定义为具有优先级排序的队列。

堆的常用操作见下表，方法名需要根据编程语言来确定。

方法名	描述	时间复杂度
`push()`	元素入堆	`O(logn)`
`pop()`	堆顶元素出堆	`O(logn)`
`peek()`	访问堆顶元素（大 / 小顶堆分别为最大 / 小值）	`O(1)`
`size()`	获取堆的元素数量	`O(1)`
`isEmpty()`	判断堆是否为空	`O(1)`

类似于排序算法中的“从小到大排列”和“从大到小排列”，通过修改Comparator来实现“小顶堆”与“大顶堆”之间的转换。

/* 初始化堆 */
// 初始化小顶堆
Queue<Integer> minHeap = new PriorityQueue<>();
// 初始化大顶堆（使用 lambda 表达式修改 Comparator 即可）
Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

/* 元素入堆 */
maxHeap.offer(1);
maxHeap.offer(3);
maxHeap.offer(2);
maxHeap.offer(5);
maxHeap.offer(4);

/* 获取堆顶元素 */
int peek = maxHeap.peek(); // 5

/* 堆顶元素出堆 */
// 出堆元素会形成一个从大到小的序列
peek = maxHeap.poll(); // 5
peek = maxHeap.poll(); // 4
peek = maxHeap.poll(); // 3
peek = maxHeap.poll(); // 2
peek = maxHeap.poll(); // 1

/* 获取堆大小 */
int size = maxHeap.size();

/* 判断堆是否为空 */
boolean isEmpty = maxHeap.isEmpty();

/* 输入列表并建堆 */
minHeap = new PriorityQueue<>(Arrays.asList(1, 3, 2, 5, 4));

堆的实现

下面实现的是大顶堆。若要将其转换为小顶堆，只需将所有大小逻辑判断取逆。

（1）堆的存储与表示

在二叉树章节中学习到，完全二叉树非常适合用数组来表示。由于堆正是一种完全二叉树，可以采用数组来存储堆。当使用数组表示二叉树时，元素代表节点值，索引代表节点在二叉树中的位置。节点指针通过索引映射公式来实现。

如下图所示，给定索引i，其左子节点索引为2i + 1，右子节点索引为2i + 2，父节点索引为(i - 1) / 2（向下取整）。当索引越界时，表示空节点或节点不存在。

先将索引映射公式封装成函数，方便后续使用。

/* 获取左子节点索引 */
int left(int i) {
    return 2 * i + 1;
}

/* 获取右子节点索引 */
int right(int i) {
    return 2 * i + 2;
}

/* 获取父节点索引 */
int parent(int i) {
    return (i - 1) / 2; // 向下整除
}

（2）访问堆顶元素

堆顶元素即为二叉树的根节点，也就是列表的首个元素。

/* 访问堆顶元素 */
int peek() {
    return maxHeap.get(0);
}

(3) 元素入堆

给定元素val，首先将其添加到堆底。由于val可能大于堆中其他元素，堆的成立条件可能已被破坏。因此，需要修复从插入节点到根节点的路径上的各个节点，这个操作被称为「堆化 heapify」。

从入堆节点开始，从底至顶执行堆化。如下图所示，比较插入节点与其父节点的值，如果插入节点更大，则将它们交换。然后继续执行此操作，从底至顶修复堆中的各个节点，直至越过根节点或遇到无须交换的节点时结束。（二叉树数组表示可以帮助理解）

设节点总数为n，则树的高度为O(logn)。由此可知，堆化操作的循环轮数最多为O(logn)，元素入堆操作的时间复杂度为O(logn)。

/* 元素入堆 */
void push(int val) {
    // 添加节点
    maxHeap.add(val);
    // 从底至顶堆化
    siftUp(size() - 1);
}

/* 从节点 i 开始，从底至顶堆化 */
void siftUp(int i) {
    while (true) {
        // 获取节点 i 的父节点
        int p = parent(i);
        // 当“越过根节点”或“节点无须修复”时，结束堆化
        if (p < 0 || maxHeap.get(i) <= maxHeap.get(p))
            break;
        // 交换两节点
        swap(i, p);
        // 循环向上堆化
        i = p;
    }
}

（4）堆顶元素出堆

堆顶元素是二叉树的根节点，即列表首元素。如果直接从列表中删除首元素，那么二叉树中所有节点的索引都会发生变化，这将使得后续使用堆化修复变得困难。为了尽量减少元素索引的变动，采用以下操作步骤。

交换堆顶元素与堆底元素（即交换根节点与最右叶节点）。
交换完成后，将堆底从列表中删除（注意，由于已经交换，实际上删除的是原来的堆顶元素）。
从根节点开始，从顶至底执行堆化。

如下图所示，“从顶至底堆化”的操作方向与“从底至顶堆化”相反，将根节点的值与其两个子节点的值进行比较，将最大的子节点与根节点交换。然后循环执行此操作，直到越过叶节点或遇到无须交换的节点时结束。

与元素入堆操作相似，堆顶元素出堆操作的时间复杂度也为O(logn)。

/* 元素出堆 */
int pop() {
    // 判空处理
    if (isEmpty())
        throw new IndexOutOfBoundsException();
    // 交换根节点与最右叶节点（即交换首元素与尾元素）
    swap(0, size() - 1);
    // 删除节点
    int val = maxHeap.remove(size() - 1);
    // 从顶至底堆化
    siftDown(0);
    // 返回堆顶元素
    return val;
}

/* 从节点 i 开始，从顶至底堆化 */
void siftDown(int i) {
    while (true) {
        // 判断节点 i, l, r 中值最大的节点，记为 ma
        int l = left(i), r = right(i), ma = i;
        if (l < size() && maxHeap.get(l) > maxHeap.get(ma))
            ma = l;
        if (r < size() && maxHeap.get(r) > maxHeap.get(ma))
            ma = r;
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma == i)
            break;
        // 交换两节点
        swap(i, ma);
        // 循环向下堆化
        i = ma;
    }
}

8.2 建堆操作

在某些情况下，我们希望使用一个列表的所有元素来构建一个堆，这个过程被称为“建堆操作”。

自上而下构建

首先创建一个空堆，然后遍历列表，依次对每个元素执行“入堆操作”，即先将元素添加至堆的尾部，再对该元素执行“从底至顶”堆化。

每当一个元素入堆，堆的长度就加一，因此堆是“自上而下”地构建的。

设元素数量为n，每个元素的入堆操作使用O(logn)时间，因此该建堆方法的时间复杂度为O(logn)。

自下而上构建

实际上，可以实现一种更为高效的建堆方法，共分为两步。

将列表所有元素原封不动添加到堆中。
倒序遍历堆（即层序遍历的倒序），依次对每个非叶节点执行“从顶至底堆化”。

在倒序遍历中，堆是“自下而上”地构建的，需要重点理解以下两点。

叶节点没有子节点，无需对它们执行堆化。最后一个节点的父节点是最后一个非叶节点。
在倒序遍历中，能够保证当前节点之下的子树已经完成堆化（已经是合法的堆），而这是堆化当前节点的前置条件。

/* 构造方法，根据输入列表建堆 */
MaxHeap(List<Integer> nums) {
    // 将列表元素原封不动添加进堆
    maxHeap = new ArrayList<>(nums);
    // 堆化除叶节点以外的其他所有节点
    for (int i = parent(size() - 1); i >= 0; i--) {
        siftDown(i);
    }
}

8.3 Top-K 问题

给定一个长度为n无序数组nums，请返回数组中前k大的元素。

遍历解法

通过k轮遍历，分别在每轮中提取第1、2、...、k大的元素，时间复杂度为O(nk)。此方法只适用于k << n的情况，因为当k与n比较接近时，其时间复杂度趋向于O(n^2)。

排序解法

可以先对数组nums进行排序，再返回最右边的k个元素，时间复杂度为O(nlogn)。显然，该方法“超额”完成任务了，因为只需要找出最大的k个元素即可，而不需要排序其他元素。

堆解法

可以基于堆更加高效地解决Top-K问题，流程如下所示。

初始化一个小顶堆，其堆顶元素最小。
先将数组的前k个元素依次入堆。
从第k + 1个元素开始，若当前元素大于堆顶元素，则将堆顶元素出堆，并将当前元素入堆。
遍历完成后，堆中保存的就是最大的k个元素。

总共执行了n轮入堆和出堆，堆的最大长度为k，因此时间复杂度为O(nlogk)。该方法的效率很高，当 k较小时，时间复杂度趋向O(n)。当k较大时，时间复杂度不会超过O(nlogn)。

另外，该方法适用于动态数据流的使用场景。在不断加入数据时，可以持续维护堆内的元素，从而实现最大k个元素的动态更新。

/* 基于堆查找数组中最大的 k 个元素 */
Queue<Integer> topKHeap(int[] nums, int k) {
    Queue<Integer> heap = new PriorityQueue<Integer>();
    // 将数组的前 k 个元素入堆
    for (int i = 0; i < k; i++) {
        heap.offer(nums[i]);
    }
    // 从第 k+1 个元素开始，保持堆的长度为 k
    for (int i = k; i < nums.length; i++) {
        // 若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆
        if (nums[i] > heap.peek()) {
            heap.poll();
            heap.offer(nums[i]);
        }
    }
    return heap;
}

9. 图

9.1 图

「图 graph」是一种非线性数据结构，由「顶点 vertex」和「边 edge」组成。我们可以将图G抽象地表示为一组顶点V和一组边E的集合。以下示例展示了一个包含5个顶点和7条边的图。

V = {1, 2, 3, 4, 5}
E = {(1, 2), (1, 3), (1, 5), (2, 3), (2, 4), (2, 5), (4, 5)}
G = {V, E}

如果将顶点看作节点，将边看作连接各个节点的引用，就可以将图看作是一种从链表拓展而来的数据结构。相较于线性关系（链表）和分治关系（树），网络关系（图）的自由度更高，从而更为复杂。

图常见类型与术语

根据边是否具有方向，可分为「无向图 undirected graph」和「有向图 directed graph」。

在无向图中，边表示两顶点之间的“双向”连接关系，例如微信中的“好友关系”。
在有向图中，边具有方向性，即A -> B和B -> A两个方向的边是相互独立的，例如微博或抖音上的“关注”与“被关注”关系。

根据所有顶点是否连通，可分为「连通图 connected graph」和「非连通图 disconnected graph」。

对于连通图，从某个顶点出发，可以到达其余任意顶点。
对于非连通图，从某个顶点出发，至少有一个顶点无法到达。

还可以为边添加“权重”变量，从而得到「有权图 weighted graph」。

图数据结构包含以下常用术语。

「邻接 adjacency」：当两顶点之间存在边相连时，称这两顶点“邻接”。上图中，顶点1的邻接顶点为顶点2、3、5。
「路径 path」：从顶点A到顶点B经过的边构成的序列被称为从A到B的“路径”。上图中，边序列1-5-2-4是顶点1到顶点4的一条路径。
「度 degree」：一个顶点拥有的边数。对于有向图，「入度 In-Degree」表示有多少条边指向该顶点，「出度 Out-Degree」表示有多少条边从该顶点指出。

图的表示

图的常用表示方式包括“邻接矩阵”和“邻接表”。以下使用无向图进行举例。

（1）邻接矩阵

设图的顶点数量为n，「邻接矩阵 adjacency matrix」使用一个n * n大小的矩阵来表示图，每一行（列）代表一个顶点，矩阵元素代表边，用1或0表示两个顶点之间是否存在边。

如下图所示，设邻接矩阵为M、顶点列表为V，那么矩阵元素M[i, j] = 1表示顶点V[i]到顶点V[j]之间存在边，反之M[i, j] = 0表示两顶点之间无边。

邻接矩阵具有以下特性。

顶点不能与自身相连，因此邻接矩阵主对角线元素没有意义。
对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称。
将邻接矩阵的元素从1和0替换为权重，则可表示有权图。

使用邻接矩阵表示图时，可以直接访问矩阵元素以获取边，因此增删查操作的效率很高，时间复杂度均为O(1)。然而，矩阵的空间复杂度为O(n^2)，内存占用较多。

（2）邻接表

「邻接表 adjacency list」使用n个链表来表示图，链表节点表示顶点。第i条链表对应顶点i，其中存储了该顶点的所有邻接顶点（即与该顶点相连的顶点）。

邻接表仅存储实际存在的边，而边的总数通常远小于n^2，因此它更加节省空间。然而，在邻接表中需要通过遍历链表来查找边，因此其时间效率不如邻接矩阵。

观察上图，邻接表结构与哈希表中的“链式地址”非常相似，因此也可以采用类似方法来优化效率。比如当链表较长时，可以将链表转化为AVL树或红黑树，从而将时间效率从O(n)优化至O(logn)。还可以把链表转换为哈希表，从而将时间复杂度降低至O(1)。

9.2 图基础操作

图的基础操作可分为对“边”的操作和对“顶点”的操作。在“邻接矩阵”和“邻接表”两种表示方法下，实现方式有所不同。

基于邻接矩阵的实现

给定一个顶点数量为n的无向图，则各种操作的实现方式如下图所示。

添加或删除边：直接在邻接矩阵中修改指定的边即可，使用O(1)时间。而由于是无向图，因此需要同时更新两个方向的边。
添加顶点：在邻接矩阵的尾部添加一行一列，并全部填0即可，使用O(n)时间。
删除顶点：在邻接矩阵中删除一行一列。当删除首行首列时达到最差情况，需要将(n - 1)^2个元素“向左上移动”，从而使用O(n^2)时间。
初始化：传入n个顶点，初始化长度为n的顶点列表vertices，使用O(n)时间。初始化n * n大小的邻接矩阵adjMat，使用O(n^2)时间。

以下是基于邻接矩阵表示图的实现代码。

/* 基于邻接矩阵实现的无向图类 */
class GraphAdjMat {
    List<Integer> vertices; // 顶点列表，元素代表“顶点值”，索引代表“顶点索引”
    List<List<Integer>> adjMat; // 邻接矩阵，行列索引对应“顶点索引”

    /* 构造方法 */
    public GraphAdjMat(int[] vertices, int[][] edges) {
        this.vertices = new ArrayList<>();
        this.adjMat = new ArrayList<>();
        // 添加顶点
        for (int val : vertices) {
            addVertex(val);
        }
        // 添加边
        // 请注意，edges 元素代表顶点索引，即对应 vertices 元素索引
        for (int[] e : edges) {
            addEdge(e[0], e[1]);
        }
    }

    /* 获取顶点数量 */
    public int size() {
        return vertices.size();
    }

    /* 添加顶点 */
    public void addVertex(int val) {
        int n = size();
        // 向顶点列表中添加新顶点的值
        vertices.add(val);
        // 在邻接矩阵中添加一行
        List<Integer> newRow = new ArrayList<>(n);
        for (int j = 0; j < n; j++) {
            newRow.add(0);
        }
        adjMat.add(newRow);
        // 在邻接矩阵中添加一列
        for (List<Integer> row : adjMat) {
            row.add(0);
        }
    }

    /* 删除顶点 */
    public void removeVertex(int index) {
        if (index >= size())
            throw new IndexOutOfBoundsException();
        // 在顶点列表中移除索引 index 的顶点
        vertices.remove(index);
        // 在邻接矩阵中删除索引 index 的行
        adjMat.remove(index);
        // 在邻接矩阵中删除索引 index 的列
        for (List<Integer> row : adjMat) {
            row.remove(index);
        }
    }

    /* 添加边 */
    // 参数 i, j 对应 vertices 元素索引
    public void addEdge(int i, int j) {
        // 索引越界与相等处理
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j)
            throw new IndexOutOfBoundsException();
        // 在无向图中，邻接矩阵沿主对角线对称，即满足 (i, j) == (j, i)
        adjMat.get(i).set(j, 1);
        adjMat.get(j).set(i, 1);
    }

    /* 删除边 */
    // 参数 i, j 对应 vertices 元素索引
    public void removeEdge(int i, int j) {
        // 索引越界与相等处理
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j)
            throw new IndexOutOfBoundsException();
        adjMat.get(i).set(j, 0);
        adjMat.get(j).set(i, 0);
    }

    /* 打印邻接矩阵 */
    public void print() {
        System.out.print("顶点列表 = ");
        System.out.println(vertices);
        System.out.println("邻接矩阵 =");
        PrintUtil.printMatrix(adjMat);
    }
}

基于邻接表的实现

设无向图的顶点总数为n、边总数为m，则可根据下图所示的方法实现各种操作。

添加边：在顶点对应链表的末尾添加边即可，使用O(1)时间。因为是无向图，所以需要同时添加两个方向的边。
删除边：在顶点对应链表中查找并删除指定边，使用O(m)时间。在无向图中，需要同时删除两个方向的边。
添加顶点：在邻接表中添加一个链表，并将新增顶点作为链表头节点，使用O(1)时间。
删除顶点：需遍历整个邻接表，删除包含指定顶点的所有边，使用O(n + m)时间。
初始化：在邻接表中创建n个顶点和m条边，使用O(n + m)时间。

下面是基于邻接表实现图的代码示例。注意，在邻接表中使用Vertex节点类来表示顶点，这样做是有原因的。

如果选择通过顶点值来区分不同顶点，那么值重复的顶点将无法被区分。
如果类似邻接矩阵那样，使用顶点列表索引来区分不同顶点。那么，想要删除索引为i的顶点，则需要遍历整个邻接表，将其中> i的索引全部减1，这样操作效率较低。
引入顶点类Vertex，使得每个顶点都是唯一的对象，此时删除顶点时就无须改动其余顶点了。

/* 基于邻接表实现的无向图类 */
class GraphAdjList {
    // 邻接表，key: 顶点，value：该顶点的所有邻接顶点
    Map<Vertex, List<Vertex>> adjList;

    /* 构造方法 */
    public GraphAdjList(Vertex[][] edges) {
        this.adjList = new HashMap<>();
        // 添加所有顶点和边
        for (Vertex[] edge : edges) {
            addVertex(edge[0]);
            addVertex(edge[1]);
            addEdge(edge[0], edge[1]);
        }
    }

    /* 获取顶点数量 */
    public int size() {
        return adjList.size();
    }

    /* 添加边 */
    public void addEdge(Vertex vet1, Vertex vet2) {
        if (!adjList.containsKey(vet1) || !adjList.containsKey(vet2) || vet1 == vet2)
            throw new IllegalArgumentException();
        // 添加边 vet1 - vet2
        adjList.get(vet1).add(vet2);
        adjList.get(vet2).add(vet1);
    }

    /* 删除边 */
    public void removeEdge(Vertex vet1, Vertex vet2) {
        if (!adjList.containsKey(vet1) || !adjList.containsKey(vet2) || vet1 == vet2)
            throw new IllegalArgumentException();
        // 删除边 vet1 - vet2
        adjList.get(vet1).remove(vet2);
        adjList.get(vet2).remove(vet1);
    }

    /* 添加顶点 */
    public void addVertex(Vertex vet) {
        if (adjList.containsKey(vet))
            return;
        // 在邻接表中添加一个新链表
        adjList.put(vet, new ArrayList<>());
    }

    /* 删除顶点 */
    public void removeVertex(Vertex vet) {
        if (!adjList.containsKey(vet))
            throw new IllegalArgumentException();
        // 在邻接表中删除顶点 vet 对应的链表
        adjList.remove(vet);
        // 遍历其他顶点的链表，删除所有包含 vet 的边
        for (List<Vertex> list : adjList.values()) {
            list.remove(vet);
        }
    }

    /* 打印邻接表 */
    public void print() {
        System.out.println("邻接表 =");
        for (Map.Entry<Vertex, List<Vertex>> pair : adjList.entrySet()) {
            List<Integer> tmp = new ArrayList<>();
            for (Vertex vertex : pair.getValue())
                tmp.add(vertex.val);
            System.out.println(pair.getKey().val + ": " + tmp + ",");
        }
    }
}

效率对比

设图中共有n个顶点和m条边，下表对比了邻接矩阵和邻接表的时间和空间效率。

	邻接矩阵	邻接表（链表）	邻接表（哈希表）
判断是否邻接	`O(1)`	`O(m)`	`O(1)`
添加边	`O(1)`	`O(1)`	`O(1)`
删除边	`O(1)`	`O(m)`	`O(1)`
添加顶点	`O(n)`	`O(1)`	`O(1)`
删除顶点	`O(n^2)`	`O(n + m)`	`O(n)`
内存空间占用	`O(n^2)`	`O(n + m)`	`O(n + m)`

观察上表，似乎邻接表（哈希表）的时间与空间效率最优。但实际上，在邻接矩阵中操作边的效率更高，只需要一次数组访问或赋值操作即可。综合来看，邻接矩阵体现了“以空间换时间”的原则，而邻接表体现了“以时间换空间”的原则。

9.3 图的遍历

树代表的是“一对多”的关系，而图则具有更高的自由度，可以表示任意的“多对多”关系。因此，可以把树看作是图的一种特例。显然，树的遍历操作也是图的遍历操作的一种特例。

图和树都都需要应用搜索算法来实现遍历操作。图的遍历方式可分为两种，「广度优先搜索 breadth-first search」和「深度优先搜索 depth-first search」，简称BFS和DFS。

广度优先遍历

广度优先遍历是一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外扩张。如下图所示，从左上角顶点出发，先遍历该顶点的所有邻接顶点，然后遍历下一个顶点的所有邻接顶点，以此类推，直至所有顶点访问完毕。

（1）算法实现

BFS通常借助队列来实现。队列具有“先入先出”的性质，这与BFS的“由近及远”的思想异曲同工。

将遍历起始顶点startVet加入队列，并开启循环。
每轮迭代中，弹出队首顶点并记录访问，然后将该顶点的所有邻接顶点加入到队列尾部。
循环上面步骤，直到所有顶点被访问完成后结束。

为了防止重复遍历顶点，需要借助一个哈希表visited来记录哪些节点已被访问。

/* 广度优先遍历 BFS */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
List<Vertex> graphBFS(GraphAdjList graph, Vertex startVet) {
    // 顶点遍历序列
    List<Vertex> res = new ArrayList<>();
    // 哈希表，用于记录已被访问过的顶点
    Set<Vertex> visited = new HashSet<>();
    visited.add(startVet);
    // 队列用于实现 BFS
    Queue<Vertex> que = new LinkedList<>();
    que.offer(startVet);
    // 以顶点 vet 为起点，循环直至访问完所有顶点
    while (!que.isEmpty()) {
        Vertex vet = que.poll(); // 队首顶点出队
        res.add(vet);            // 记录访问顶点
        // 遍历该顶点的所有邻接顶点
        for (Vertex adjVet : graph.adjList.get(vet)) {
            if (visited.contains(adjVet))
                continue;        // 跳过已被访问过的顶点
            que.offer(adjVet);   // 只入队未访问的顶点
            visited.add(adjVet); // 标记该顶点已被访问
        }
    }
    // 返回顶点遍历序列
    return res;
}

广度优先遍历的序列是否唯一? 答案是不唯一。广度优先遍历只要求按“由近及远”的顺序遍历，而多个相同距离的顶点的遍历顺序是允许被任意打乱的。顶点1、3的访问顺序可以交换。

（2）复杂度分析

时间复杂度：所有顶点都会入队并出队一次，使用O(|V|)时间。在遍历邻接顶点的过程中，由于是无向图，因此所有边都会被访问2次，使用O(2|E|)时间。总体使用O(|V| + |E|)时间。

空间复杂度：列表res，哈希表visited，队列queue中的顶点数量最多为|V|，使用O(|V|)空间。

深度优先遍历

深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。如下图所示，从左上角顶点出发，访问当前顶点的某个邻接顶点，直到走到尽头时返回，再继续走到尽头并返回，以此类推，直至所有顶点遍历完成。

（1）算法实现

这种“走到尽头再返回”的算法范式通常基于递归来实现。与广度优先遍历类似，在深度优先遍历中也需要借助一个哈希表visited来记录已被访问的顶点，以避免重复访问顶点。

/* 深度优先遍历 DFS 辅助函数 */
void dfs(GraphAdjList graph, Set<Vertex> visited, List<Vertex> res, Vertex vet) {
    res.add(vet);     // 记录访问顶点
    visited.add(vet); // 标记该顶点已被访问
    // 遍历该顶点的所有邻接顶点
    for (Vertex adjVet : graph.adjList.get(vet)) {
        if (visited.contains(adjVet))
            continue; // 跳过已被访问过的顶点
        // 递归访问邻接顶点
        dfs(graph, visited, res, adjVet);
    }
}

/* 深度优先遍历 DFS */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
List<Vertex> graphDFS(GraphAdjList graph, Vertex startVet) {
    // 顶点遍历序列
    List<Vertex> res = new ArrayList<>();
    // 哈希表，用于记录已被访问过的顶点
    Set<Vertex> visited = new HashSet<>();
    dfs(graph, visited, res, startVet);
    return res;
}