114. 二叉树展开为链表
一句话套路先序展开:左子树右端接右子树
题目描述
给你二叉树的根结点 root ,请你将它展开为一个单链表:
- 展开后的单链表应该同样使用
TreeNode,其中right子指针指向链表中下一个结点,而左子指针始终为null。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1:
输入:root = [1,2,5,3,4,null,6] 输出:[1,null,2,null,3,null,4,null,5,null,6]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [0] 输出:[0]
提示:
- 树中结点数在范围
[0, 2000]内 -100 <= Node.val <= 100
进阶:你可以使用原地算法(O(1) 额外空间)展开这棵树吗?
思路
时间
O(n)空间
O(1)思路
思路(原地,O(1) 空间):对每个有左子树的结点,找到「左子树最右结点」(前驱),把当前右子树挂到前驱右边,再把左子树整体搬右,左置空,然后下移。
这本质是 Morris 遍历的变形。
另解
反后序(右->左->根)+ 一个 prev 指针,一行一行地接,也很好记。
图解
二叉树(来自本仓库测试数据,
nullopt 表示空位)C++17 题解
namespace lc0114 {
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode* cur = root;
while (cur) {
if (cur->left) {
TreeNode* pred = cur->left;
while (pred->right) pred = pred->right; // 前驱 = 左子树最右
pred->right = cur->right;
cur->right = cur->left;
cur->left = nullptr;
}
cur = cur->right;
}
}
// 测试辅助:沿 right 走一遍取值,同时确认 left 全空
static vector<int> rightSpine(TreeNode* root, bool& allLeftEmpty) {
vector<int> out;
allLeftEmpty = true;
for (TreeNode* p = root; p; p = p->right) {
if (p->left) allLeftEmpty = false;
out.push_back(p->val);
}
return out;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0114::Solution s;
TreeNode* a = buildTree({1, 2, 5, 3, 4, nullopt, 6});
s.flatten(a);
bool leftEmpty = false;
CHECK_EQ(s.rightSpine(a, leftEmpty), vector<int>{1, 2, 3, 4, 5, 6});
CHECK_TRUE(leftEmpty);
freeTree(a);
TreeNode* b = buildTree({});
bool e2 = true;
CHECK_EQ(s.rightSpine(b, e2), vector<int>{});
TreeNode* c = buildTree({0});
s.flatten(c);
bool e3 = false;
CHECK_EQ(s.rightSpine(c, e3), vector<int>{0});
CHECK_TRUE(e3);
freeTree(c);