树 | Ziuch の Blog

type

status

date

slug

summary

0. 本节习题一览

完全二叉树 树的遍历：958. 二叉树的完全性检验

完全二叉树二分+位运算：222. 完全二叉树的节点个数

前序遍历习题1：144. 二叉树的前序遍历

中序遍历习题：94. 二叉树的中序遍历

后序遍历习题：145. 二叉树的后序遍历

前序遍历习题2：589. N 叉树的前序遍历

递归+非递归实现：606. 根据二叉树创建字符串

根据遍历序列恢复二叉树1：105. 从前序与中序遍历序列构造二叉树

根据遍历序列恢复二叉树2：106. 从中序与后序遍历序列构造二叉树

层序遍历习题1：102. 二叉树的层序遍历

层序遍历习题2：103. 二叉树的锯齿形层序遍历

层序遍历习题3：429. N 叉树的层序遍历

恢复二叉搜索树：1008. 前序遍历构造二叉搜索树

递归+非递归判别二叉搜索树：98. 验证二叉搜索树

哈希，中序遍历+双指针：653. 两数之和 IV - 输入二叉搜索树

中序遍历+哈希优化：230. 二叉搜索树中第K小的元素

字典树习题1：1268. 搜索推荐系统

字典树习题2：1803. 统计异或值在范围内的数对有多少

1. 树/二叉树

1.1 概念

💡

树有且仅有一个根结点，除根结点外的所有结点有且只有一个前驱

💡

n个结点的树中有n-1条边

💡

结点拥有的子树的数量是为节点的度，树的度为树内所有节点度的最大值

💡

二叉树即度为2的树，二叉树的子树有左右之分，并以以递归的形式定义

💡

树的存储表示有：双亲表示法(并查集)，孩子表示法(同时也可以用来存图)，孩子兄弟表示法

1.2 二叉树的存储表示

1.2.1 顺序表示法

💡

用下标从1开始的列表进行存储

💡

设当前节点的下标为i，那么左儿子的下标为2 * i，右儿子的下标为2 * i + 1，父节点的下标为i / 2

💡

会有大量的存储空间浪费，满二叉树和完全二叉树则不存在浪费的情况

1.2.2 链式表示法

💡

链式表示法内的节点定义是递归的

1.3 特殊的二叉树

1.3.1 斜树/单支树(链表)

💡

每个节点都仅含左/右孩子

1.3.2 满二叉树

💡

除最后一层节点外，所有节点都有左右儿子

1.3.3 完全二叉树

💡

节点类似于按照书写顺序排列，或者说按照数组存储的下标排列

💡

有n个节点的完全二叉树，最后一个有孩子的节点下标为n / 2

💡

堆就是一颗完全二叉树，它是通过数组进行存储的

完全二叉树 树的遍历：958. 二叉树的完全性检验

完全二叉树二分+位运算：222. 完全二叉树的节点个数

1.4 二叉树的遍历

1.4.1 前序(深度优先遍历 DFS)/中序/后序遍历

💡

三种遍历算法每个结点都访问一次且仅访问一次，故时间复杂度都是O(n)

💡

递归工作栈的栈深恰好为树的深度，所以在最坏情况下，二叉树是有n个结点的斜树，遍历算法的空间复杂度为O(n)

简易二叉树递归遍历代码模板：

通用二叉树递归遍历代码模板：

二叉树非递归遍历代码模板：

前序遍历习题1：144. 二叉树的前序遍历

中序遍历习题：94. 二叉树的中序遍历

后序遍历习题：145. 二叉树的后序遍历

前序遍历习题2：589. N 叉树的前序遍历

递归+非递归实现：606. 根据二叉树创建字符串

根据遍历序列恢复二叉树1：105. 从前序与中序遍历序列构造二叉树

根据遍历序列恢复二叉树2：106. 从中序与后序遍历序列构造二叉树

1.4.2 层序遍历(广度/宽度优先遍历 BFS)

代码模板：

层序遍历习题1：102. 二叉树的层序遍历

层序遍历习题2：103. 二叉树的锯齿形层序遍历

层序遍历习题3：429. N 叉树的层序遍历

2. 二叉搜索/排序树

💡

左孩子比父节点小，右孩子比父节点大

💡

二叉搜索树的中序遍历是有序的

💡

树的形状和插入顺序有关

💡

查找的平均时间复杂度为O(logn)，最坏情况下为O(n)

恢复二叉搜索树：1008. 前序遍历构造二叉搜索树

递归+非递归判别二叉搜索树：98. 验证二叉搜索树

哈希，中序遍历+双指针：653. 两数之和 IV - 输入二叉搜索树

中序遍历+哈希优化：230. 二叉搜索树中第K小的元素

3. 字典树/Trie/前缀树

💡

利用字符串的公共前缀,在存储时节约存储空间,并在查询时最大限度的减少无谓的比较

💡

可以看作是一颗26叉树(可根据题意拓展)

💡

树的形状和插入顺序无关，每次查找的比较次数与字符串个数无关，只和字符串长度有关

💡

需要用一个变量标记字符串的结尾，即是否有某个字符串在此结束

代码模板：

字典树习题1：1268. 搜索推荐系统

字典树习题2：1803. 统计异或值在范围内的数对有多少

4 树状数组

💡

在O(logn)的时间内维护可单点修改的前缀和

💡

lowbit(x): x的二进制的最后一个1代表的数

💡

橙色矩形表示树状数组中的每个元素，灰色矩形则示意其后接的每个树状数组元素所能“管理”的范围。

💡

根据元素下标的 lowbit值，可将各元素分层，形式上看上去像是一颗树一样的结构（如图虚线所示）

💡

原数组为A，构建出的树状数组为tree，下标均从 1 开始，二者满足如下关系

模版

init

lowbit(x)

add

update

query

sumRange

1. 数组不变，求区间和：「前缀和」、「树状数组」、「线段树」 2. 多次修改某个数（单点），求区间和：「树状数组」、「线段树」 3. 多次修改某个区间，输出最终结果：「差分」 4. 多次修改某个区间，求区间和：「线段树」、「树状数组」（看修改区间范围大小） 5.多次将某个区间变成同一个数，求区间和：「线段树」，「树状数组」（看修改区间范围大小）

这样看来，「线段树」能解决的问题是最多的，那我们是不是无论什么情况都写「线段树」呢？答案并不是，而且恰好相反，只有在我们遇到第4类问题，不得不写「线段树」的时候，我们才考虑线段树。

因为「线段树」代码很长，而且常数很大，实际表现不算很好。我们只有在不得不用的时候才考虑「线段树」。

总结一下，我们应该按这样的优先级进行考虑： 1. 简单求区间和，用「前缀和」 2. 多次将某个区间变成同一个数，用「线段树」 3. 其他情况，用「树状数组」

5 线段树

6 树上倍增最近公共祖先

1483. 树节点的第 K 个祖先

一、思考

最暴力的做法是，从 node 出发，一步一步地往上跳

需要跳 k 次才能到达 node 的第 k 个祖先节点，时间复杂度为 O(k)。

如何优化这个暴力算法呢？

一个初步的想法是，预处理出每个节点的「爷爷节点」，即父节点的父节点，那么就可以两步两步地往上跳，从而减少一半的跳跃次数（循环次数）。

进一步地，再预处理出爷爷节点的爷爷节点，就可以四步四步地往上跳。

请你思考：一般地，要预处理出哪些节点呢？如何利用这些预处理出的节点，快速地找到第 k 个祖先节点？

二、解惑

预处理出每个节点的第 2^i 个祖先节点，即第 1, 2, 4, 8, ⋯ 个祖先节点（其中 x 的第 1 个祖先节点就是 parent[x]）。由于任意 k 可以分解为若干不同的 2 的幂（例如 13 = 8 + 4 + 1），所以只需要预处理出这些 2^i 祖先节点，就可以快速地到达任意第 k 个祖先节点。

例如 k=13=8+4+1=1101(2)，我们可以先往上跳 8 步，再往上跳 4 步和 1 步；也可以先往上跳 1 步，再往上跳 4 步和 8 步。无论如何跳，都只需要跳 3 次就能到达第 13 个祖先节点。

据此，可以得到下面的算法。

三、算法

在构造函数 TreeAncestor 中，预处理出每个节点 x 的第 2^i 个祖先节点，记作 pa[x][i]（若第 2^i 个祖先节点不存在，则 pa[x][i] = -1）。计算方式如下：

先枚举 i，再枚举 x。相当于先算出所有爷爷节点，再算出所有爷爷节点的爷爷节点，依此类推。

pa[x][0] = parent[x]，即父节点。

pa[x][1] = pa[pa[x][0]][0]，即爷爷节点。

依此类推，pa[x][i+1] = pa[pa[x][i]][i]，表示 x 的第 2^i 个祖先节点的第 2^i 个祖先节点就是 x 的第 2^(i+1) 个祖先节点。特别地，如果 pa[x][i] = -1 则 pa[x][i+1] = -1。

这里 i+1 至多为 ⌊log2 n⌋。例如 n=13 时，⌊log2 13⌋=3，至多需要预处理到第 2^3 个祖先节点。（当然，你也可以先把树高，或者每个节点的深度求出来，再据此做精细地计算。）

对于 getKthAncestor，需要找到 k 的二进制表示中的所有 1（相当于把 k 分解为若干 2^i）。可以从小到大枚举 i，如果 k 右移 i 位后的最低位为 1，就说明 k 的二进制从低到高第 i 位是 1，那么往上跳 2^i 步，将 node 更新为 pa[node][i]。如果 node = -1 则说明第 k 个祖先节点不存在。

代码中用到了一些位运算技巧，具体请看从集合论到位运算，常见位运算技巧分类总结！

Python3 示例

复杂度分析

时间复杂度：预处理 O(nlogn)，回答每个询问 O(logk)。

空间复杂度：预处理需要 O(nlogn) 的空间。

注：利用长链剖分，可以做到预处理 O(nlogn)，回答每个询问 O(1) 的时间复杂度。

Python3 示例

复杂度分析

时间复杂度：预处理 O(nlogn)，回答每个询问 O(logn)。

空间复杂度：预处理需要 O(nlogn) 的空间。

0. 本节习题一览

1. 树/二叉树

1.1 概念

1.2 二叉树的存储表示

1.2.1 顺序表示法

1.2.2 链式表示法

1.3 特殊的二叉树

1.3.1 斜树/单支树(链表)

1.3.2 满二叉树

1.3.3 完全二叉树

1.4 二叉树的遍历

1.4.1 前序(深度优先遍历 DFS)/中序/后序遍历

1.4.2 层序遍历(广度/宽度优先遍历 BFS)

2. 二叉搜索/排序树

3. 字典树/Trie/前缀树

4 树状数组

5 线段树

6 树上倍增 最近公共祖先

一、思考

二、解惑

三、算法

Python3 示例

复杂度分析

最近公共祖先

Python3 示例

复杂度分析

6 树上倍增最近公共祖先