高效获取电子教材：智能下载工具完整使用手册
2026/1/16 5:33:10
二叉树的问题往往千变万化，但归根结底是对遍历顺序和指针操作的掌控。
今天我们要探讨两道非常有代表性的题目：
二叉树的右视图：如何通过巧妙的 DFS 遍历顺序，捕捉特定视角的节点？
二叉树展开为链表：如何在不使用额外空间的情况下，对树的结构进行“大手术”？
本文将基于 C++ 代码，深度解析这两类问题的解题模版与核心思维。
一、 视角的艺术：二叉树的右视图
1. 题目与思路解析
题目要求我们返回从二叉树右侧能看到的节点值。直观上，这似乎需要层序遍历（BFS）取每一层的最后一个元素。但其实，利用DFS（深度优先搜索）可以写出更简洁的代码。
核心策略：
反向中序遍历：传统的先序遍历是“中 -> 左 -> 右”，如果我们改为“中 -> 右 -> 左”，那么对于每一层来说，我们最先访问到的一定是这一层最右边的节点。
深度标记：利用 depth 变量记录当前深度。如果 ans 数组的大小等于当前深度，说明我们第一次到达这一层，也就是找到了这一层的最右节点。
2. 代码实现
C++代码实现：
class Solution { vector<int> ans; void dfs(TreeNode* root, int depth) { if (root == nullptr) return; // 核心逻辑：ans.size() == depth 说明这是第一次到达该深度 // 因为我们优先走了右边，所以这就是最右边的点 if (ans.size() == depth) { ans.push_back(root->val); } // 优先递归右子树 dfs(root->right, depth + 1); // 注意这里是值传递递归，不是引用&，所以是不需要恢复现场的 dfs(root->left, depth + 1); } public: vector<int> rightSideView(TreeNode* root) { // 思路： 其实就是看右边的树的高度能否覆盖掉左边的树，换句话说如果答案的长度等于树的高度也就是加入ans dfs(root, 0); return ans; } };3. 深度分析：为什么不需要“恢复现场”？
代码中有一句非常有价值的注释：注意这里是值传递递归，不是&，所以是不需要恢复现场的。
这是一个非常关键的知识点。
不需要回溯：我们在调用
dfs(root->right, depth + 1)时，depth + 1是作为一个临时值传给下一层的。当前层手中的 depth 变量并没有被改变。因此，当右子树遍历结束，去遍历左子树时，我们依然使用原始的 depth 加 1 传给左边。需要回溯的情况：如果你使用的是全局变量 currentDepth 或者引用传递
int& depth，那么在从右子树出来、进入左子树之前，就必须手动depth--。
4. 复杂度分析
时间复杂度：O(N)，每个节点访问一次。
空间复杂度：O(H)，递归栈深度，最坏情况 O(N)。
二、 结构的重组：二叉树展开为链表
1. 题目与思路解析
这道题要求将二叉树原地展开为一个单链表（利用 right 指针）。顺序符合前序遍历。
难点挑战：你能否使用 O(1) 的额外空间来实现？（即不使用递归栈或额外的数组）。
核心策略：寻找前驱节点（Morris 遍历思想）我们要把“左子树”塞到“右子树”的前面。
找到当前节点 cur 的左子树中最右边的那个节点（这是 cur 在中序遍历下的前驱，也是左子树中最晚被访问的节点）。
把 cur 原本的右子树，接到这个前驱节点的右边。
把整个左子树移到 cur 的右边。
cur 向右移动，重复上述过程。
2. 代码实现
C++代码实现：
class Solution { public: void flatten(TreeNode* root) { // 思路： 要自顶向下处理才可以满足O（1）空间复杂度的要求 // 因此可以先把234看作一个整体连在15中间，然后继续处理左子树 TreeNode* cur = root; while (cur) { // 只有左边有东西才需要搬运 if(cur->left) { // 1. 找左子树的最右节点 (接盘侠) TreeNode* p = cur->left; while (p->right) p = p->right; // 2. 把当前节点的右子树，嫁接到左子树最右节点的后面 p->right = cur->right; // 3. 把左子树整体挪到右边 cur->right = cur->left; // 4. 左边置空，防止双重指向 cur->left = nullptr; } // 继续处理链表的下一个节点 cur = cur->right; } } };3. 深度分析：指针的乾坤大挪移
这段代码最精彩的地方在于**“整体搬运”**。
我们看一个局部：
Plaintext：
1 / \ 2 5 / \ \ 3 4 6当 cur 指向 1 时：
找到左子树的最右节点：4。
把 1 的右子树（5-6）接到 4 的后面。
把 1 的左子树（2-3-4）挪到 1 的右边。
结构变更为：
1 -> 2 -> 3 -> 4 -> 5 -> 6。
这一过程不需要递归，仅通过修改指针就完成了树的“拉直”。
4. 复杂度分析
时间复杂度：O(N)。虽然有嵌套循环，但每个节点只会被作为“前驱节点”寻找一次，整体是线性的。
空间复杂度：O(1)。我们只用了 cur 和 p 两个指针，没有使用递归栈，完美符合进阶要求。
三、 总结
RightSideView教会我们：DFS 的顺序（先右后左）可以帮我们“抢占”每一层的特定位置，配合 depth 值传递，逻辑清晰且无需回溯。
Flatten教会我们：指针的重组可以将树降维成链表。利用前驱节点（Predecessor）的概念，我们可以实现 O(1) 空间的算法，这是对数据结构最底层的操控能力。