数据结构与算法

发表于

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭将基于 Java / Kotlin 语言，为你分享常见的数据结构与算法问题，及其解题框架思路。

本文是数据结构与算法系列的第 17 篇文章，完整文章目录请移步到文章末尾~

目录

  1. 概述

优秀的算法往往取决于采用的数据结构，在算法面试中，通常涉及较多的还是几种基础数据结构。其中树（Tree）是最常考的，也是相对难的，建议应试者优先准备关于树的面试题；

1.1 逻辑结构

从逻辑上看，树（Tree） 是一种非线性结构，树的节点包含元素值与所有子节点的列表。如果按照图的理论来说，树可以看作是一种特殊的图（N 个节点和 N - 1 条边的连通的有向无环图）；

1.2 存储结构

从存储上看，树可以采用数组 & 链表两种存储方式。链表存储法很直接明了，就是每个节点里都持有子节点的引用，而数组存储法则需要利用下标来寻找父子节点关系，节点内部不再需要持有子节点的引用，更加节约内存。

采用数组存储方式时，树的根节点可以分配在数组第 [0] 位，也可以分配在第 [1] 位，两种方式没有明显的区别，主要是计算子节点 / 父节点下标的公式有所不同：

根节点存储在第 [0] 位

  1. 对于第 [i] 位上的节点，第 [2 * i +1] 位是左节点，第 [2 * i + 2] 位是右节点
  2. 对于第 [i] 位上的节点，第 [(i-1) / 2] 位是父节点

根节点存储在第 [1] 位

  1. 第 [0] 位不存储，根节点存储在第 [1] 位
  2. 对于第 [i] 位上的节点，第 [2 * i] 位是左节点，第[2 * i + 1] 位是右节点
  3. 对于第 [i] 位上的节点，第 [i / 2] 位是父节点

需要注意的是，完全二叉树采用数组存储方式是空间利用率最高的。

—— 引用自 time.geekbang.org/column/arti… 王争 著

  1. 树的遍历

树的遍历是树最最重点的知识，也是常考的点，因为在解决其他问题的时候，通常就需要遍历整棵树来寻找答案，所以我们必须对 树的各种遍历方式 非常熟悉（特别是二叉树的遍历）。总结常见的题目，可以将遍历一棵树的方式分为：

  • 前序遍历（DFS）
  • 中序遍历（DFS）
  • 后序遍历（DFS）
  • 层序遍历（BFS）
  • 路径遍历（热门）
  • 垂序遍历（冷门）

—— 引用自 LeetCode

2.1 前序遍历 & 中序遍历 & 后序遍历

这三种遍历的区别：访问到一个节点时，处理当前节点与处理左右子树的顺序不同。在前序遍历中，访问节点顺序与处理节点顺序是一致的，而另外两种是不一致的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
scss复制代码Preorder (root) {
  1. access content of root 
  2. Call Preorder(root.left)
  3. Call Preorder(root.right)
}

Postorder (root) {
  1. Call Postorder(root.left)
  2. Call Postorder(root.right)
  3. access content of root
}

Inorder (root) {
  1. Call Inorder(root.left) 
  2. access content of root
  3. Call Inorder(root.right)
}
  • 递归解法

递归解法可以说很简单了，就是调整左右子树的递归顺序即可：

  • 非递归解法

BFS 的非递归解法需要利用栈的 LIFO 特性：

复杂度分析：

  • 时间复杂度：O(n)O(n)O(n)
  • 空间复杂度：树退化链表时最差O(n)O(n)O(n)、树平衡时最优O(lgn)O(lgn)O(lgn)，平均O(lgn)O(lgn)O(lgn)

2.2 层序遍历

层序遍历需要利用队列的 FIFO 特性，即：每次迭代都将一整层的节点放进队列里，如下图所示：

—— 引用自 leetcode-cn.com/problems/bi… nettee 著

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
kotlin复制代码fun levelOrder(root: TreeNode?): List<List<Int>> {
        val result = ArrayList<List<Int>>()

        val queue: Queue<TreeNode> = LinkedList()

        if (null != root) {
            queue.offer(root)
        }

        while (!queue.isEmpty()) {
            val level = ArrayList<Int>()
            // 处理一层
            for (index in 0 until queue.size) {
                val node = queue.poll()
                level.add(node.`val`)
                if (null != node.left) {
                    queue.offer(node.left)
                }
                if (null != node.right) {
                    queue.offer(node.right)
                }
            }
            if (level.isNotEmpty()) {
                result.add(level)
            }
        }
        return result
    }

另外，层序遍历也是常见的变型题，例如自底向上、锯齿形，其实无非就是改变输出结果的步骤：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
scss复制代码- 锯齿形：

var flag = true

for(...){
    if(flag){
        level.add(node.`val`)
    }else{
        level.addFirst(node.`val`)
    }
}
...
flag = !flag

- 自底向上：

for(...){
    ...
}

result.addFirst(level)

复杂度分析：

  • 时间复杂度：O(n)O(n)O(n)
  • 空间复杂度：树退化链表时最差O(n)O(n)O(n)、树平衡时最优O(lgn)O(lgn)O(lgn)，平均O(lgn)O(lgn)O(lgn)

2.3 路径遍历

路径遍历其实是前面四种遍历的升级版，无非就是将经过的节点记录到String。下图的 DFS 解法使用了最简单的前序遍历方法：

复杂度分析：

  • 时间复杂度：需要复制字符串，O(n2)O(n^2)O(n2)
  • 空间复杂度：树退化链表时最差O(n2)O(n^2)O(n2)、树平衡时最优O((lgn)2)O((lgn)^2)O((lgn)2)，平均O((lgn)2)O((lgn)^2)O((lgn)2)

2.4 垂序遍历

  • 本节对应题目：
+ [987. Vertical Order Traversal of a Binary Tree 二叉树的垂序遍历](https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/)
  1. 树的概念

通常来说不会直接考察树的相关概念，但是理解清楚这些概念是解决其他复杂问题的基础。

—— 引用自 time.geekbang.org/column/arti… 王争 著

  • 路径：从一个节点走到另一个节点的经过的节点；
  • 距离：通常指最短距离，即两个节点到最近共同祖先的路径和；
  • 高度：从节点到叶子节点的路径；
  • 深度：从节点到根节点的路径；
  • 宽度：每层两个端点（该层最左和最右的非空节点，两端点间的 null 节点也计入长度）之间的长度。
  1. 递归思想

经常地，一棵树要满足某种性质，都会要求它的每个节点也都满足该性质，例如对于一棵二叉搜索树，从它的每棵子树观察，都是一棵二叉搜索树；或者，当解一棵树的最终解时，一般可先求出左右两棵子树的最终解，再结合当前节点求出最终解，

通用的解题模板 & 思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
kotlin复制代码var result = Integer.MIN_VALUE 或 0

fun search(node : TreeNode) : Int{
    1. 左子树最终解
    val leftResult = search(node.left)

    2. 右子树最终解
    val rightResult = search(node.right)

    3. 结合当前节点得出当前解
    val bestResult = ...

    4. 更新最优解 result

    5. 返回当前解
}

例如：求二叉树的最大深度。要求一棵树的最大深度，如果已知左右两个子树的最大深度，那么很明显这棵树的最大深度，就是两棵子树结果的最大值再加一。所以这个问题用递归就很轻松可以解决，当然是用层序遍历也能解决：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
kotlin复制代码参考代码 1
fun maxDepth(root: TreeNode?): Int {
    if (root == null) {
        return 0
    } else {
        val leftHeight = maxDepth(root.left)
        val rightHeight = maxDepth(root.right)
        return Math.max(leftHeight, rightHeight) + 1
    }
}
参考代码 2
fun maxDepth(root: TreeNode?): Int {
    fun search(root: TreeNode?, parentDepth: Int): Int {
        if (root == null) {
            return parentDepth
        } else {
            val leftHeight = search(root.left, parentDepth + 1)
            val rightHeight = search(root.right, parentDepth + 1)
            return Math.max(leftHeight, rightHeight)
        }
    }
    return search(root, 0)
}

这两段代码看起来差不多，其实本质上是有较大不同的。参考代码 1 中，+ 运算是在子节点执行的，而参考代码 2 中，+ 是在父节点执行的。也就是说，参考代码 1 更适合于 “整合子问题的解得到最终解” 的思路，而参考代码 2 更适合于 “将父节点的状态传递给子节点”的思路。

  1. 路径问题

前面我们定义了路径的概念：从一个节点走到另一个节点的经过的节点，这一节我们专门讨论路径相关的问题。

5.1 向下的路径（从根到叶子的路径）

这一类问题找出一条满足某个条件的路径，要求路径是从根节点到叶子节点。这等于是指明了路径的起始点和终止点，因此这类问题只需要按照 第2.3节 - 路径遍历 即可轻松解决。

5.2 向下的路径（非必须从根到叶子的路径）

这一类问题不要求路径是从根节点到叶子节点，可以经过也可以不经过。因此路径的起始点和终止点就不确定了，难度会稍稍增大，那么应该怎么解呢？这就要引入 前缀和 的概念。

假设我们要找和为 10 的路径，我们可以逐步记录访问到节点的前缀和，当我们访问到一个点（记为 B），它的前缀和 - 目标和 正好与之前记录的一个前缀和相同（记为 A），说明从 A 到 B 之间经过的路径和正好就是目标和：

5.3 自由路径

这一类题目不再要求路径是从上到下的，选择的可能性更多，例如下图中经过 A 节点的路径总共有 4 条：

那么这类问题应该怎么解呢？还记得我们说的 递归思想 吗？我们要求这棵树的最优解，假设我们已求得左右两颗子树的解，那么再结合当前节点求出最终解。例如：124. Binary Tree Maximum Path Sum 二叉树的最大路径和

在这道题里，不要求路径是从上向下的，也不要求结果一定要经过根节点，所以是不满足最优子结构的。但是我们可以转换一下，先假设结果是经过根节点的，使其满足最优子结构：给定一棵树，假设已知左子树和右子树的最大路径和，那么对于当前树，最大路径和就是两棵子树结果最大值加上根节点的值。当然，根节点的最大路径和不一定是整棵树的最大路径和，因此我们需要使用一个变量记录录得的最大值。

  1. 祖先问题

6.1 最近共同祖先

6.2 最远共同祖先

  1. 特殊的树

前面我们将的树都是普通的二叉树，下面讨论常见的几种特殊的二叉树：

7.1 满二叉树

满二叉树中，叶子节点全部在最底层，即：除了叶子节点外，每个节点都拥有左节点和右节点。对于一棵满二叉树，从任意一个子树看都是满二叉树。

编号 2 为满二叉树

—— 引用自 time.geekbang.org/column/arti… 王争 著

7.2 完全二叉树

完全二叉树中，叶子节点都在最后两层，并且最后一层的节点都靠左排列。对于一棵完全二叉树，从任意一个子树看都是完全二叉树。

—— 引用自 time.geekbang.org/column/arti… 王争 著

7.3 二叉搜索树

二叉搜索树中，对于任意节点的值来说，都大于左子树中每个节点的值，都小于右子树中每个节点的值。对于一棵二叉搜索树，从任意一个子树看都是二叉搜索树。

—— 引用自 time.geekbang.org/column/arti… 王争 著

7.4 平衡二叉树

平衡二叉树中，对于任意节点来说，左右子树的高度差不大于1。对于一棵平衡二叉树，从任意一个子树看都是平衡二叉树。

平衡二叉树避免了二叉树左右子树高度相差太大是时间和空间复杂度退化的问题。但需要注意的是，在实践中使用的是“近似平衡”，只需要保证左右子树高度相对平均，并不需要严格准守高度差不大于 1 的定义。

—— 引用自 time.geekbang.org/column/arti… 王争 著

7.5 平衡二叉搜索树

平衡二叉搜索树有很多种，例如伸展树（Splay Tree）、树堆（Treap）、红黑树（AVL），其中红黑树是最常见的。

  1. 构建二叉树
  • 本节相关问题：

从前序和中序遍历构造二叉树

从中序和后序遍历构造二叉树

从前序遍历构造二叉树

从前序和后序遍历构造二叉树

构建高度最小的树

构建二叉搜索树

  1. 总结
    1. 树的遍历解决树问题的基本编程技巧，必须熟练掌握递归与非递归两种写法；
    1. 树的概念是理解题意的前提，必须保证理解清晰，没有混淆；
    1. 递归思想非常适用于解决树问题，当你遇到一个问题没有解题思路时，应该先想想：如果你知道左右两个子树（子问题）的答案，是否能清晰的解决当前树的问题；
    1. 树的路径 & 祖先问题是面试中的常客。
树的遍历 提示 & 题解
144. 二叉树的前序遍历 Binary Tree Preorder Traversal 【题解】
94. 二叉树的中序遍历 Binary Tree Inorder Traversal 【题解】
145. 二叉树的后序遍历 Binary Tree Postorder Traversal 【题解】
589. N 叉树的前序遍历 N-ary Tree Preorder Traversal 【题解】
590. N 叉树的后序遍历 N-ary Tree Postorder Traversal 【题解】
404. 左叶子之和 Sum of Left Leaves 【题解】
树的层序遍历 提示 & 题解
102. 二叉树的层序遍历 Binary Tree Level Order Traversal 【题解】
107. 二叉树的层序遍历（自底向上） Binary Tree Level Order Traversal II 【题解】
103. 二叉树的层序遍历（锯齿） Binary Tree Zigzag Level Order Traversal 【题解】
429. N 叉树的层序遍历 N-ary Tree Level Order Traversal 【题解】
513. 找树左下角的值 Find Bottom Left Tree Value 【题解】
树的路径遍历 提示 & 题解
257. 二叉树的所有路径 Binary Tree Paths 【题解】
树的概念 提示 & 题解
111. 二叉树的最小深度 Minimum Depth of Binary Tree 【题解】
104. 二叉树的最大深度 Maximum Depth of Binary Tree 【题解】
559. 叉树的最大深度 Maximum Depth of N-ary Tree N 【题解】
662. Maximum Width of Binary Tree 二叉树的最大宽度
树的路径 提示 & 题解
257. 二叉树的所有路径 Binary Tree Paths 【题解】
112. 路径总和 I Path Sum 【题解】
129. 从根到叶子节点数字之和 Sum Root to Leaf Numbers 【题解】
437. 路径总和 III Path Sum III 【题解】
1367. 二叉树中的列表 Linked List in Binary Tree
572. 另一个树的子树 Subtree of Another Tree
124. 二叉树的最大路径和 Binary Tree Maximum Path Sum 【题解】
687. 最长同值路径 Longest Univalue Path 【题解】
祖先问题 提示 & 题解
236. 二叉树的最近共同祖先 Lowest Common Ancestor of a Binary Tree 【题解】
1123. 最深叶节点的最近共同祖先 Lowest Common Ancestor of Deepest Leaves 【题解】
235. 二叉搜索树的最近共同祖先 Lowest Common Ancestor of a Binary Search Tree 【题解】
1483. 树节点的第 k 个祖先 Kth Ancestor of a Tree Node
1026. 节点与其祖先的最大差值 Maximum Difference Between Node and Ancestor 【题解】
特殊的树 提示 & 题解
958. 验证完全二叉树 Check Completeness of a Binary Tree
04.04. 验证平衡二叉树 Check Balance LCCI
98. 验证二叉搜索树 Validate Binary Search Tree

参考资料

推荐阅读

数据结构与算法系列完整目录如下（2023/07/11 更新）：

Java & Android 集合框架系列文章: 跳转阅读

LeetCode 上分之旅系列文章：跳转阅读

⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%