type
status
date
slug
summary
tags
category
icon
password
Last edited time
Jun 2, 2024 08:45 AM
😀
树与二叉树，树的遍历，二叉搜索树，字典树，树状数组，线段树，树上倍增

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 斜树/单支树(链表)

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

1.3.2 满二叉树

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

1.3.3 完全二叉树

💡
节点类似于按照书写顺序排列，或者说按照数组存储的下标排列
💡
有n个节点的完全二叉树，最后一个有孩子的节点下标为n / 2
💡
堆就是一颗完全二叉树，它是通过数组进行存储的
notion image
完全二叉树 树的遍历：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叉树(可根据题意拓展)
💡
树的形状和插入顺序无关，每次查找的比较次数与字符串个数无关，只和字符串长度有关
💡
需要用一个变量标记字符串的结尾，即是否有某个字符串在此结束
notion image
代码模板：
字典树习题1：1268. 搜索推荐系统
字典树习题2：1803. 统计异或值在范围内的数对有多少

4 树状数组

💡
在O(logn)的时间内维护可单点修改的前缀和
💡
lowbit(x): x的二进制的最后一个1代表的数
notion image
💡
橙色矩形表示树状数组中的每个元素，灰色矩形则示意其后接的每个树状数组元素所能“管理”的范围。
💡
根据元素下标的 lowbit值，可将各元素分层，形式上看上去像是一颗树一样的结构（如图虚线所示）
notion image
💡
原数组为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) 的时间复杂度。

最近公共祖先

如何计算树上任意两点 x 和 y 的最近公共祖先 lca 呢？
设节点 i 的深度为 depth[i]。这可以通过一次 DFS 预处理出来。
假设 depth[x] ≤ depth[y]（否则交换两点）。我们可以先把更靠下的 y 更新为 y 的第 depth[y] - depth[x] 个祖先节点，这样 x 和 y 就处在同一深度了。
如果此时 x=y，那么 x 就是 lca。否则说明 lca 在更上面，那么就把 x 和 y 一起往上跳。
由于不知道 lca 的具体位置，只能不断尝试，先尝试大步跳，再尝试小步跳。设 i=⌊log2 n⌋，循环直到 i<0。每次循环：
  • 如果 x 的第 2^i 个祖先节点不存在，即 pa[x][i] = -1，说明步子迈大了，将 i 减 1，继续循环。
  • 如果 x 的第 2^i 个祖先节点存在，且 pa[x][i] ≠ pa[y][i]，说明 lca 在 pa[x][i] 的上面，那么更新 x 为 pa[x][i]，更新 y 为 pa[y][i]，将 i 减 1，继续循环。否则，若 pa[x][i] = pa[y][i]，那么 lca 可能在 pa[x][i] 下面，由于无法向下跳，只能将 i 减 1，继续循环。
上述做法能跳就尽量跳，不会错过任何可以上跳的机会。所以循环结束时，x 与 lca 只有一步之遥，即 lca = pa[x][0]。

Python3 示例

复杂度分析

  • 时间复杂度：预处理 O(nlogn)，回答每个询问 O(logn)。
  • 空间复杂度：预处理需要 O(nlogn) 的空间。
 
相关文章
数据结构与算法讲义(Python版)
OJ快速入门
Python语法补充
Python常用数据类型
图
线性结构
图线性结构
Loading...