leetcode 链接：二叉树展开为链表

题目

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例：
[中等] 114. 二叉树展开为链表 - 图1

  1. 输入：root = [1,2,5,3,4,null,6]
  2. 输出：[1,null,2,null,3,null,4,null,5,null,6]
  1. 输入：root = []
  2. 输出：[]
  1. 输入：root = [0]
  2. 输出：[0]

解答 & 代码

解法一：后序遍历

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {   
  13. public:
  14.     void flatten(TreeNode* root) {
  15.         // 递归结束条件
  16.         if(root == nullptr)
  17.             return;
  19.         // 1. 递归将左、右子树展开为链表
  20.         flatten(root->left);
  21.         flatten(root->right);
  23.         /**** 后序位置 ****/
  24.         TreeNode* left = root->left;
  25.         TreeNode* right = root->right;
  27.         // 2. 将 root 的左子树作为链表的下一个节点（right）
  28.         root->left = nullptr;
  29.         root->right = left;
  31.         // 3. 定位到 root 原左子树的末端，将其 right 指向 root 原右子树头部
  32.         TreeNode* cur = root;
  33.         while(cur->right != nullptr)
  34.             cur = cur->right;
  35.         cur->right = right;
  36.     }
  37. };

复杂度分析：？

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 85.36% 的用户
  4. 内存消耗：12.4 MB, 在所有 C++ 提交中击败了 43.05% 的用户

解法二：前序遍历

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {   
  13. private:
  14.     TreeNode* pre;        // 当前遍历到的节点的前一个节点
  15.     // 前序遍历二叉树，同时展开为链表
  16.     void preOrder(TreeNode* root)
  17.     {
  18.         // 递归结束条件
  19.         if(root == nullptr)
  20.             return;
  22.         // 先序位置：处理当前节点
  23.         pre->right = root;                // 将前一节点和当前节点相连
  24.         TreeNode* left = root->left;    // 左子树节点
  25.         TreeNode* right = root->right;    // 右子树节点
  26.         root->left = nullptr;            // 将当前节点的左子树置空
  27.         pre = root;                        // 更新前一节点 pre 为当前节点 root
  29.         // 递归处理左、右子树
  30.         preOrder(left);
  31.         preOrder(right);
  32.     }
  33. public:
  34.     void flatten(TreeNode* root) {
  35.         TreeNode* dummyHead = new TreeNode();
  36.         pre = dummyHead;    // 初始化 pre 为虚拟头节点
  37.         preOrder(root);
  38.     }
  39. };

复杂度分析：设二叉树共 N 个节点

  • 时间复杂度 O(N)：遍历每个节点一次
  • 空间复杂度 O(log N)：栈空间取决于递归深度，即二叉树的高度

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 85.36% 的用户
  4. 内存消耗：12.4 MB, 在所有 C++ 提交中击败了 57.12% 的用户