114. 二叉树展开为链表
3 min
题目
解法：Morris遍历
思路
核心思想是Morris遍历变种：对每个节点，将其左子树的最右节点连接到右子树，然后将左子树移到右侧。
正确性证明：该算法通过寻找左子树前驱节点，确保了左子树的所有节点都先于右子树被访问，保持了先序遍历的根-左-右顺序。每次迭代都将当前节点的左子树正确插入到右子树之前，并保证链表不断裂，最终形成完整的单链表结构。
- Step 1: 初始化cur为根节点
- Step 2: 当cur不为空时循环
- Step 3: 若cur有左子树，找到其最右节点pre
- Step 4: 将pre->right指向cur->right
- Step 5: 将cur->right指向cur->left
- Step 6: 将cur->left置为nullptr
- Step 7: cur移动到cur->right继续处理
复杂度
- 时间复杂度:
- 空间复杂度:
代码
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode* cur = root;
while (cur) {
if (cur->left) {
TreeNode* pre = cur->left;
while (pre->right) {
pre = pre->right;
}
pre->right = cur->right;
cur->right = cur->left;
cur->left = nullptr;
}
cur = cur->right;
}
}
};