0114. Flatten Binary Tree to Linked List
=======================================
题目信息
--------
:题号: 0114. 二叉树展开为链表
:难度: Medium
:主题: 二叉树、前序遍历、原地重连、反向递归
:原题: `LeetCode 0114 `_
:重点: 从保存前序节点序列后重连,推导到反向前序维护后继,再用局部前驱接续实现常量工作空间
题目重述
--------
给定二叉树根节点 ``root``,直接修改原树,把所有节点展开成一条只沿 ``right`` 指针连接的单向链。链中节点
顺序必须与原树的前序遍历“根、左子树、右子树”一致,并且每个节点的 ``left`` 都必须置为 ``nullptr``。
函数不返回新链表,原根仍是展开后链的起点;不能用新建节点替换输入节点。空树无需操作。树中节点总数在
``0..2000`` 范围内,节点值在 ``-100..100`` 范围内。
自建示例
--------
* 左右子树都存在:``root = [8,4,12,2,6,10,null]``,修改后右链为
``8 -> 4 -> 2 -> 6 -> 12 -> 10``;
* 左孩子内部仍有左支:``root = [1,2,5,3,null,null,6,4]``,修改后右链为
``1 -> 2 -> 3 -> 4 -> 5 -> 6``;
* 单节点:``root = [7]``,节点保持为链首且 ``left == nullptr``;
* 空树:``root = []``,不执行任何重连。
C++ 实现
--------
.. code-block:: cpp
#include
class Solution {
private:
void collectPreorder(TreeNode* node, std::vector& nodes) {
if (!node) {
return;
}
nodes.push_back(node);
collectPreorder(node->left, nodes);
collectPreorder(node->right, nodes);
}
void collectThenRelink(TreeNode* root) {
std::vector nodes;
collectPreorder(root, nodes);
for (int index = 0; index < static_cast(nodes.size()); ++index) {
nodes[index]->left = nullptr;
nodes[index]->right = index + 1 < static_cast(nodes.size()) ? nodes[index + 1] : nullptr;
}
}
void linkInReversePreorder(TreeNode* node, TreeNode*& next) {
if (!node) {
return;
}
linkInReversePreorder(node->right, next);
linkInReversePreorder(node->left, next);
node->right = next;
node->left = nullptr;
next = node;
}
void reversePreorderRelink(TreeNode* root) {
TreeNode* next = nullptr;
linkInReversePreorder(root, next);
}
void predecessorRelink(TreeNode* root) {
TreeNode* current = root;
while (current) {
if (current->left) {
TreeNode* predecessor = current->left;
while (predecessor->right) {
predecessor = predecessor->right;
}
predecessor->right = current->right;
current->right = current->left;
current->left = nullptr;
}
current = current->right;
}
}
public:
void flatten(TreeNode* root) {
predecessorRelink(root);
}
};
题解
----
目标序列再重连
~~~~~~~~~~~~~~
最直接的正确方案是先执行前序遍历,把原节点指针依次保存到数组,再按数组顺序重写指针。若数组为
``[p0,p1,...,pk]``,就令每个 ``pi.left = nullptr``、``pi.right = p(i+1)``,最后一个节点右指针为空。
``collectThenRelink`` 将“确定目标顺序”和“修改结构”分成两个阶段。收集期间不改树,所以递归始终能找到
原左右孩子;重连期间只操作已经保存的节点指针,不创建、遗漏或复制节点。这版逻辑清楚,但数组保存了完整
前序序列,使用 ``O(n)`` 工作空间。
原地处理的困难不是前序遍历本身,而是过早覆盖指针会丢失尚未访问的子树。要删除节点数组,必须在修改
``node->right`` 之前,已经有另一种状态能保留它原本应接到的位置。
反向前序后继
~~~~~~~~~~~~
目标链的前序顺序为“根、左、右”。反过来处理就是“右、左、根”。若递归先完成右子树、再完成左子树,
处理当前节点时,变量 ``next`` 已经指向当前节点在最终前序链中的直接后继:有左子树时是左子树根,否则是
右子树根,再否则是此前构造好的更后方节点或空指针。
``linkInReversePreorder`` 因而执行:
.. code-block:: text
先递归 right
再递归 left
node.right = next
node.left = null
next = node
右子树先被连成后缀,左子树随后接到这个后缀之前,当前根最后接到最前面。原先需要保存全部节点的数组被
压缩为一个 ``next`` 指针和递归调用栈;调用顺序若改成先左后右,构造出的后继顺序就会颠倒。
局部前驱接续
~~~~~~~~~~~~
还可以不等待递归回溯,而是在当前节点就把局部结构改成前序顺序。若 ``current`` 没有左孩子,它的下一个
前序节点本来就是 ``current->right``,只需沿右链前进。
若左孩子存在,当前节点之后应先访问整棵左子树,原右子树必须排在左子树之后。沿左子树的 ``right`` 指针
找到最右节点 ``predecessor``;它的右指针当前为空,可暂存原右子树入口。三次重连按顺序为:
.. code-block:: text
predecessor->right = current->right
current->right = current->left
current->left = nullptr
第一步必须发生在覆盖 ``current->right`` 之前,否则原右子树入口会丢失。完成后,沿 ``current->right``
首先进入原左子树;该子树以后进行同样重连时,只会把自己的左部分插到已有右后缀之前,不会丢弃后缀,因而
原右子树最终仍位于整个左子树的前序节点之后。
这里的 ``predecessor`` 是当前左子树沿已有右指针能到达的最右节点,不必预先就是左子树最终前序链的末尾。
若它内部还有左支,后续局部重连会把已接上的原右子树继续向后传递。算法依赖的是“空右指针可保存后缀”,
不是错误地假设当前右边界已经完成展平。
重连走读
~~~~~~~~
对 ``[8,4,12,2,6,10,null]``:
.. list-table::
:header-rows: 1
* - ``current``
- 左子树右边界
- 保存的旧右子树
- 重连后的局部右链
* - 8
- 6
- 12
- ``8 -> 4``,且 ``6 -> 12``
* - 4
- 2
- 6
- ``4 -> 2 -> 6``
* - 2
- 无左子树
- 不变
- ``2 -> 6``
* - 6
- 无左子树
- 不变
- ``6 -> 12``
* - 12
- 10
- 空
- ``12 -> 10``
外层循环每次沿已经形成的 ``right`` 前序链移动。所有左子树都在到达父节点时搬到这条链上,每次搬动后又
清空父节点的 ``left``,所以最终不会跳过节点,也不会留下非空左指针。
主解与复杂度
~~~~~~~~~~~~
公开入口采用前驱接续法,因为它复用原树中的空右指针保存后缀,不需要节点数组或递归栈。输入各子树原本
互不相交,把左子树右边界连接到原右子树不会形成回指祖先的环。
收集后重连时间 ``O(n)``、数组空间 ``O(n)``;反向前序时间 ``O(n)``、递归栈 ``O(h)``。前驱接续中,
外层沿最终右链访问每个节点一次,内层沿右边界的总访问量为线性摊还,时间 ``O(n)``、额外空间 ``O(1)``。
三种方法都只重用原节点,返回结构本身不新增空间。