HHot 100C++ 图解

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 指针,一行一行地接,也很好记。

图解

3 2 4 1 5 6
二叉树(来自本仓库测试数据,nullopt 表示空位)

C++17 题解

src/08_binary_tree.cpp29 行
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;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q114_flatten16 行
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);

↑↓ 选择↵ 打开/ 随时唤起