力扣刷题笔记 #13 树

本文包含「树」类型题中的：前中后序遍历、层序遍历、树高和树深、树上路径问题、二叉搜索树、N 叉树等。持续更新中。

题目描述：

方法1：

方法2：

方法3：

坑点：

树的定义天然具有递归的性质，因此许多树的问题都可以用递归方法来解决。

这里提到的「树」大多以指针的形式存储，如果要用数组存储也可以。

前中后序遍历

144. 二叉树的前序遍历 (E)

题目描述：给定二叉树的根节点 root，返回它节点值的前序遍历。

方法1：递归，输出中间节点，再递归遍历左子树、右子树。时间复杂度 \(O(n)\)，空间复杂度平均 \(O(\log n)\)，最坏情况下（链状）为 \(O(n)\)。

方法2：迭代，模拟栈，根节点入栈，当栈不为空时弹出栈顶元素，再压入右节点、左节点。复杂度同上。

方法3：Morris 遍历，利用树的大量空指针实现空间开销的极限缩减。时间复杂度 \(O(n)\)，空间复杂度平均 \(O(1)\)。

构建 Morris 树：以某个根节点开始，找到它左子树的最右侧节点之后与这该根节点进行连接（用末尾的空指针指向根节点）。

遍历 Morris 树：用一个 cur 指针，从根节点开始按照「左 ... 左 + 右 ... 右」的顺序遍历，即可回到根节点，并访问完整个左子树。然后 cur 向右走一步，重复以上操作，直到右指针为空。

坑点：如果需要将完整遍历结果放到一个向量中返回，因此函数传参时要传引用调用。

94. 二叉树的中序遍历 (E)

题目描述：给定二叉树的根节点 root，返回它节点值的中序遍历。

方法1：递归，时间复杂度 \(O(n)\)，空间复杂度平均 \(O(\log n)\)，最坏情况下（链状）为 \(O(n)\)。

方法2：迭代，模拟栈，但不能像前序、后序那样简单地将两个子节点都入栈，而是需要一路向左！

一路向左：先入栈，root 向左移，满足「左-中-右」顺序。

左移到空：说明到了最左边的尽头，此时可以弹出栈顶元素作为 root，并打印，满足「左-中-右」顺序。

向右一步：root 向右移，然后再入栈，满足「左-中-右」顺序。重复以上三步。

右移到空：说明这个左子树已经遍历结束，此时可以弹出栈顶元素 root，并打印，满足「左-中-右」顺序。

105. 从前序与中序遍历序列构造二叉树 (M)

题目描述：给定两个整数数组 preorder 和 inorder，均无重复元素，构造二叉树并返回其根节点。

方法1：递归，前序遍历的第一个元素为根节点，可以将中序遍历一分为二，分别得到左右子树的中序遍历长度，对应到前序遍历，得到 l1, r1, l2, r2 四个下标继续递归。时间复杂度 \(O(n^2)\)。

方法2：递归 + 哈希表，找根节点的过程由于无重复元素，可以先用哈希表记录每个元素在中序序列的下标，时间复杂度优化到 \(O(n)\)，空间复杂度 \(O(n)\)。

方法3：迭代，模拟递归的工作栈，过于复杂暂且不表。

114. 二叉树展开为链表 (M)

题目描述：给定二叉树的根节点，将其以先序遍历顺序展开为单链表，链表用 TreeNode 实现，只使用右指针。

方法1：递归，维护 pre 表示「前驱节点」，每次递归时，先将根节点放入链表，而 pre 更新为根节点。递归展开左子树，此时 pre 会走到左子树的最右节点，也是右子树的前驱节点。接着递归展开右子树。总复杂度 \(O(n)\)。

方法2：迭代，维护 cur 表示「当前节点」，对于一个没有左子树的点，可以直接跳过；否则，注意到左子树的最右节点就是右子树的前驱节点，直接将右子树拼接到此处，并将左子树移到 cur 的右子树，将 cur 的左指针置空。继续迭代下一个节点。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

297. 二叉树的序列化与反序列化 (H)

题目描述：实现两个方法，将一个二叉树序列化为连续的字符串结构，并采用相反方式反序列化得到二叉树。

方法：DFS 先序遍历，序列化时将节点值输出为 val, 将空指针输出为 None, 逗号作为分隔符。采用先序递归即可。反序列化时先将字符串 split 为数组，再递归先序建树，可以直接顺序扫描。

Todo表达式计算

用中序遍历容易得到原始表达式，但计算机并不方便计算。如果用后序遍历，使用栈来处理表达式会变得更加容易。 每遇到一个操作符，就可以从栈中弹出栈顶的两个元素，计算并将结果返回到栈中。

遍历并修改

通过递归调用自身，可以简洁地实现整个过程，需要注意的是：修改的步骤可能要放在子树操作的前、中、后。

101. 对称二叉树 (E)

题目描述：给定一个二叉树的根节点 root ， 检查它是否轴对称。

方法：镜像遍历，DFS 传入 root->left 和 root->right，子问题是判断 left->left 和 right->right 是否镜像、判断 left->right 和 right->left 是否镜像。时间复杂度 \(O(n)\)。

坑点：进入 DFS 后要判断空，只有两个指针都非空才向深处 DFS。

226. 翻转二叉树 (E)

题目描述：给定一棵二叉树的根节点 root，镜像翻转这棵二叉树，并返回其根节点。

方法：DFS 先序遍历，先对左右子树进行翻转，再将当前节点的左右子节点交换即可，复杂度 \(O(n)\)。

坑点：本题不能镜像遍历，因为不能保证对称位置也有节点，直接先序遍历即可。注意交换时要用临时变量保存中间值。

617. 合并二叉树 (E)

题目描述：给定两棵二叉树的根节点，将两棵树合并：如果两个节点重合，则节点值相加；否则不为空的节点直接作为新节点。

方法1：DFS，先判断当前比对的两个节点是否有空节点，如果有就返回另一个节点；否则就递归合并左、右子树，并将合并后的答案都指向 root1 作为返回值。复杂度 \(O(n)\)。

层序遍历

基础模板，使用队列存储：

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    queue<TreeNode*> q;
    if(root) q.push(root);
    while(!q.empty()){
        int n = q.size();
        res.push_back(vector<int> {});
        while(n--){
            TreeNode* temp = q.front();
            q.pop();
            res.back().push_back(temp->val);
            if(temp->left) q.push(temp->left);
            if(temp->right) q.push(temp->right);
        }
    }
    return res;
}

102. 二叉树的层序遍历 (M)

题目描述：给定二叉树的根节点 root，逐层地从左到右访问所有节点。

方法1：BFS，维护一个队列，当队列不为空时，出队并将子节点入队。时空复杂度均为 \(O(n)\)。

方法2：DFS，传参时传入 depth 和 res 数组，将节点放到 res[depth] 中即可。空间复杂度为 \(O(\log n)\)。

坑点：输出结果时需要分层，因此 BFS 可以在遍历每层的时候先记录下当前栈里的元素个数（该层的元素个数），再 while(n--) 遍历当前层。DFS 在传参时传入 depth 即可。

103. 二叉树的锯齿形层序遍历 (M)

题目描述：给定二叉树的根节点 root，先从左往右，再从右往左逐层遍历，层与层之间交替方向。

方法：BFS + 双端队列，奇数层右进左出，偶数层左进右出，时空复杂度均为 \(O(n)\)。

199. 二叉树的右视图 (M)

题目描述：给定一个二叉树的 根节点 root，按照从顶部到底部的顺序，返回站在右侧所能看到的节点值。

方法：BFS，维护一个队列，用两个 while 分层，每层的最后一个节点保存。时空复杂度均为 \(O(n)\)。

515. 在每个树行中找最大值 (M)

题目描述：给定一个二叉树的 根节点 root，返回该二叉树中每一层的最大值。

方法：BFS，维护一个队列，用两个 while 分层，每层的维护一个最大值。时空复杂度均为 \(O(n)\)。

2415. 反转二叉树的奇数层 (M)

题目描述：给定一颗满二叉树，反转这棵树中每个奇数层的节点值（左右镜像）。

方法1：DFS，遍历两次，第一次按层数存下所有节点，第二次按层数赋值节点。时空复杂度均为 \(O(n)\)。

方法2：BFS + 层序遍历，用两个双端队列存下左右两侧的节点，两侧的出队方向不同，只需遍历一次。

方法3：DFS + 镜像遍历，DFS 传参不再是传 root，而是传入 root->left 和 root->right，每次 DFS 的子问题分别是交换 left->left 和 right->right、交换 left->right 和 right->left。

树的属性

一次 DFS 可以求出树的属性包括：深度、节点数、每个节点的父节点。

两次 DFS 可以求出树的属性包括：直径。

104. 二叉树的最大深度 (E)

题目描述：给定一个二叉树，找出其最大深度，即根节点到最远叶子节点路径上的节点数。

方法1：递归，如果当前为空指针，返回 0。否则递归调用自身求出左右子树的最大深度，并加 1 返回。复杂度 \(O(n)\)。

方法2：BFS + 层序遍历，每一层深度加一。复杂度 \(O(n)\)。

2831. 移除子树后的二叉树高度 (H)

题目描述：二叉树的中有 \(n<1e5\) 个节点，每个节点被分配 \(1\) 到 \(n\) 的不同值，给定 \(m<1e4\) 个查询，每次查询删除掉某个节点的所有子树后，整个树的高度（一个节点高度为 0）。

方法1：DFS 暴力，第一次 DFS 维护每个节点的 \(height\)，父节点及兄弟节点编号。每次查询时再自底向上回溯，先看有无兄弟，如果有兄弟再看兄弟的高度分类讨论。时间复杂度 \(O(nm)\)，超时。

方法2：两次 DFS + 树形 DP，第一次 DFS 自底向上回溯算出 \(height\)，第二次 DFS 自顶向下算出 \(depth\)，同时在第二次 DFS 中，还可以自顶向下处理出答案，最后查询时直接取答案即可。时间复杂度 \(O(n)\)。

设删掉节点 root 的所有子树后的高度为 \(restH\)，则删掉其左子树的所有子树后整个树的高度有两种可能：

• 不包含 root 节点的路径最长：则这条节点贡献的高度就是 \(restH\)；
• 包含 root 节点的路径最长：则这条路径肯定来自 root 的右子树，因此就是此时 root 的 \(depth\) 加上右子树的 \(height\)。

其中 \(restH\) 只与父节点有关，因此可以自顶向下计算，这时一种 DP 的思想。

方法3：转 DFS 序 + 前缀处理，先 DFS 遍历并按顺序存下遍历过的节点编号（DFS 序），并预处理出每个节点的深度，并存储每个节点管辖的子树区间。每次删除点就相当于删除一段连续区间，并将原数组分为两段，分别代表子树的左侧和右侧。两端区间中每个节点深度的最大值即为答案，因此先预处理前缀和后缀 MAX，总时间复杂度 \(O(n)\)。

从 DFS 序来看，同一棵子树节点所对应的 DFS 序是连续的一段区间，每个节点管辖的子树区间会紧跟着该节点。

如何求管辖区间？用一个全局变量 \(idx\) 记录当前的点的 DFS 序，在每次 DFS 过程中，子树区间始于 \(idx+1\)，并在 DFS 左子树和右子树后，新的 \(idx\) 就是右端点。

树上路径问题

543. 二叉树的直径 (E)

题目描述：一棵二叉树的直径长度是任意两个结点路径长度中的最大值，等价于树上最长路径经过节点数减一。

方法：DFS，任意一条路径可以看作「左路径 + 右路径」拼接而成，在这里左路径就是左子树的深度，右路径同理。因此只需递归计算深度，同时在回溯到每个节点时维护最大值即可。时间复杂度 \(O(n)\)，空间复杂度 \(O(Depth)\)。

Todo. 1245. 树的直径 (M)

题目描述：给定一棵无向树（N 叉、任意节点可以作为根），求树的直径。

方法1：两次 DFS，

方法2：树形 DP，

124. 二叉树中的最大路径和 (H)

题目描述：树的路径定义为不分叉的节点连线，在节点值可正可负的情况下，求最大路径和。

方法1：递归，当前节点可以作为路径的拐角，也可以组成路径的直线。前者不能再回溯，后者可以回溯给父节点，两者中的最值是当前节点的最大路径和，用于维护全局最大值。时间复杂度 \(O(n)\)。

设左子树的递归结果为 \(L\)，右子树的递归结果为 \(R\)，当前节点值为 \(V\)，则：

• 当前节点作为拐角的结果：\(\max(L,R, L+R+V)\)
• 当前节点组成路径的直线：\(\max(L+V, R+V, V)\)

两者共同维护全局最大值，同时只有后者作为返回值回溯。

236. 二叉树的最近公共祖先 (M)

题目描述：给定一个二叉树，找到该树中两个指定节点的最近公共祖先。一个节点也可以是它自己的祖先。

方法1：递归，递归函数的返回值传递一个信息「该二叉树中是否含有 P 或 Q」，具体的返回值需要分类讨论。递归一次，时间复杂度 \(O(n)\)，最坏情况下二叉树退化成链表，空间复杂度 \(O(n)\)。

1. 如果当前节点为空，则返回空，这里直接用当前节点。

2. 如果当前节点就是 P 或 Q，则分两种情况，但是都是返回当前节点：

   1. 另一个节点在当前节点的子树中，则当前节点就是答案。
   2. 另一个节点不在当前子树，说明当前节点只是其祖先节点在调用递归，需要返回一个非空值表示找到。

3. 其他情况下，P 和 Q 可能在当前节点的左、右子树中，也可能不在当前子树：

   1. 如果左、右子树的递归返回值都不为空，则 P、Q 分布在左、右子树中，当前节点就是答案。
   2. 如果只有一个子树的返回值不为空，则要么 P、Q 都在该子树，答案一定在该子树中；要么只有一个在该子树，需要返回一个非空值表示找到。都要返回递归该子树的结果。
   3. 如果都为空，则说明 P Q 不在当前子树，则返回空，这里直接用子树的递归结果。

方法2：后序遍历，由方法 1 可知，当前节点会接收子节点的状态（是否含有）并把这个状态往上传递，直到满足祖先节点的条件。所以用后序遍历的模板也可完成。复杂度均为 \(O(n)\)。

方法3：存储父节点，遍历一次二叉树并用哈希表存储每个节点的父节点，则从 P、Q 开始往上搜索，就变成了求两个链表相交点问题，再用一个哈希表或双指针即可。复杂度均为 \(O(n)\)。

二叉搜索树

二叉搜索树特性：

• 左子树小于等于父节点，右子树大于等于父节点。
• 中序遍历可以转化为有序的序列。
• 不满足平衡性，可能会退化成链表。

二叉搜索树可以 DFS 查找，也可以非递归查找，非递归速度更快，参考如下代码：

bool find(TreeNode* root, int target) {
    while (root) {
        if (root->val == target) {
            return true;
        }else if (root->val > target) {
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return false;
}

98. 验证二叉搜索树 (M)

题目描述：给定一个二叉树的根节点，判断其是否是一个有效的二叉搜索树。

方法1：递归，根节点给左子树规定了上界，给右子树规定了下界。以此类推，每次递归都会缩小边界，如果每个节点都满足祖先节点规定的边界，则其为二叉搜索树。时空复杂度均为 \(O(n)\)。

方法2：中序遍历，二叉搜索树构成的序列一定是升序的，因此在中序遍历时检查当前节点是否大于上一个节点即可。时空复杂度均为 \(O(n)\)。

669. 修剪二叉搜索树 (M)

题目描述：给定二叉搜索树的根节点 root，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在 [low, high] 中，且不改变树节点的相对结构。

方法1：递归，根据二叉搜索树的定义，root<low 时删去整个左子树，root>high 时删去整个右子树，其他时候保留两个子树。再递归处理剩下的子树，时空复杂度均为 \(O(n)\)。

方法2：迭代，从 root 出发找到第一个满足范围的节点，就是要返回的根节点。当根节点符合范围时，修剪左子树时只需考虑删除 <low 的节点，修剪右子树时只需考虑删除 >high 的节点。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

235. 二叉搜索树的最近公共祖先 (M)

题目描述：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

方法1：递归，由于二叉搜索树的性质，可以根据值的大小提前判断节点位置。因此递归无需传递信息，因为不可能的一侧必定不会展开递归，无需回溯。时空复杂度均为 \(O(n)\)。

1. 当前节点是 P 或 Q，直接返回当前节点。注意不可能出现当前节点为空的情况，因为空的一侧不可能递归到。
2. 根据节点值判断：
   1. P 和 Q 都在左子树：返回递归左子树的结果。
   2. P 和 Q 都在右子树：返回递归右子树的结果。
   3. P 和 Q 分别位于左右子树：返回当前节点。

方法2：存储父节点，复杂度均为 \(O(n)\)。

538. 把二叉搜索树转换为累加树 (M)

题目描述：给定一棵二叉搜索树，将其转换为累加树，使每个节点的新值等于原树中大于或等于当前节点的值之和。

方法1：DFS 暴力，每个节点需要加上「当前节点的右子树之和」和「祖先节点传递下来的值」。其中前者可以一次 DFS 预处理子树之和，后者需要分类讨论：对于左子节点，传递当前节点的累加值；对于右子节点，传递父节点的传递值，时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。

方法2：反序中序遍历，二叉搜索树中序遍历（左-中-右）的结果为递增序列，反序中序遍历（右-中-左）的结果为递减序列。因此反序遍历时维护一个全局变量 \(sum\)，每次都将当前节点更新为 \(sum\) 即可。复杂度 \(O(n)\)。

N 叉树

N 叉树就是广义的树，其存储和遍历规则都可以当作图来处理，唯一不同的是其还保留树的一些特性：

• 删掉任意一条边可以将整个树分割为两个连通块，即每条边都是割边。
• 从根节点开始一次 DFS 即可访问所有节点，且不会重复访问陷入死循环。

// 一维数组 nums 存点, 二维数组 edges 存边
vector<vector<int>> g(nums.size());	// 大小也可以取 edges.size() - 1
for (auto &e : edges) {
    int x = e[0], y = e[1];
    g[x].push_back(y);
    g[y].push_back(x); // 无向图，父子关系根据 root 的选择而定
}
// DFS, x 是结点编号, fa 是父节点，在无向图中防止重复遍历
function<int(int, int)> dfs = [&](int x, int fa) {
    for (int y : g[x])
        if (y != fa) {
            int res = dfs(y, x);
        }
    return res + 1;
};
// 从根节点开始 DFS，不会重复访问，父节点设为 -1
return dfs(0, -1); 

Todo 310. 最小高度树 (M)

题目描述：给定一颗 N 叉树，选择任意一个节点为根，使得树的高度最小化，返回所有最小高度树。

方法1：

方法2：

方法3：拓扑排序

坑点：

2477. 到达首都的最少油耗 (M)

题目描述：给定 \(n\) 个节点的 N 叉树，每个点代表一座城市，编号 0 的城市是首都，每个城市需要派出一名代表去往首都，期间需要乘坐汽车，可换乘，每辆汽车有 \(seats\) 个座位，求总共的最少行程。

方法：N 叉树 DFS + 贪心回溯，总共的行程等于每条边上的车数总和，因此 DFS 回溯每个节点的子节点个数（代表人数），总人数除以座位数向上取整就是边上的车数，时间复杂度 \(O(n)\)。

6294. 最大价值和与最小价值和的差值 (H)

题目描述：

方法1：N 叉树 DFS + 记忆化，

方法2：

方法3：

坑点：

Todo 2440. 创建价值相同的连通块 (H)

题目描述：

方法1：

方法2：

方法3：

坑点：