首页 > 编程语言 >力扣 114. 二叉树展开为链表-原地算法(O(1) 额外空间)详解

力扣 114. 二叉树展开为链表-原地算法(O(1) 额外空间)详解

时间:2022-10-24 19:57:21浏览次数:76  
标签:力扣 right work 链表 拼接 二叉树 null root 节点

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(1) 额外空间),那么先展开记录节点,然后再按要求建树开销就不止O(1)了,

要实现O(1)就不能额外建树。经过观察发现,展开之后的二叉树其实是先将右子树按先序遍历展开得到链表形式的树R,再将左子树按先序遍历展开树L

然后拼接成root-L-R,如root = [1,2,5,3,4,null,6],先得到树R:[5,null,6],再得到树L:[2,null,3,null,4],拼接起来是[1,null,2,null,3,null,4,null,5,null,6],

那么先编写一个函数将一棵树以链表形式展开,然后依次放入根节点的左右子树,再拼接就可以完成了。

为了节约空间复杂度,将树展开时就同时完成拼接的工作,就不用将这棵树再多存储一次了。

首先题目要求的先序遍历,根据递归写出基本代码,然后因为要同时修改节点之间的关系来完成拼接,那么就传入root节点,

void work(TreeNode* &p,TreeNode* &root) {//传入当前节点,根节点

   if(p==nullptr) { return; }

   work(p->right,root);

   work(p->left,root);

   //重新拼接 }

接下来解决拼接的部分,需要将p节点拼接到root右子树的位置上,而原右子树的位置的节点则变成p的右子树,如root-right,p=>root-p-right

那么拼接部分应该为:p->right=root->right; p->left=nullptr; root->right=p;

先令p指向root指向的右节点,然后将root指向更改为p,注意将p左子树赋值为空

 将代码与思路串联起来,先取出根节点右子树(额外空间1来存储),与根节点一起传入work函数,

再取出根节点左子树,同样传入函数,完成拼接。

完整代码
class Solution {
public:
   void work(TreeNode* &p,TreeNode* &root) {
       if(p==nullptr)
       {
          return;
       }
       work(p->right,root);
       work(p->left,root);
       p->right=root->right;
       p->left=nullptr;
       root->right=p;
   }
   void flatten(TreeNode* root) {
       if(root!=nullptr)
       {
           TreeNode *result=root->right;
           root->right=nullptr;
           work(result,root);
           result=root->left;
           root->left=nullptr;
           work(result,root);
       }
   }
};

 

标签:力扣,right,work,链表,拼接,二叉树,null,root,节点
From: https://www.cnblogs.com/fudanxi/p/16822583.html

相关文章

  • 【二叉树】两棵二叉搜索树中的所有元素
    0x00题目给你​​root1​​​和​​root2​​​这两棵二叉搜索树请你返回一个列表其中包含​​​两棵树​​​中的所有整数并按​​升序​​排序0x01思路二叉搜......
  • 【二叉树】删点成林
    0x00题目给出二叉树的根节点​​root​​​树上每个节点都有一个不同的值如果节点值在​​to_delete​​中出现我们就把该节点从树上​​删去​​最后得到一个森林(......
  • 【二叉树】二叉树中的最长交错路径
    0x00题目给你一棵以​​root​​为根的二叉树,二叉树中的交错路径定义如下:选择二叉树中​​任意​​​节点和一个方向(​​左​​​或者​​右​​​)如果前进方向为​​......
  • 【二叉树】最大层内元素和
    0x00题目给你一个二叉树的根节点​​root​​​设根节点位于二叉树的第​​1​​层而根节点的子节点位于第​​2​​层依此类推请返回层内元素之和​​​最大​​......
  • 剑指Offer-14-剪绳子/力扣-343-整数拆分
    对于一段绳子,第一刀下去可以将绳子分成i和n-i两段,其中i的取值范围为[1,n-1]dp[n]表示n可分成的最大乘积和,dp[n]=max(dp[n],max(i*n-i,i*f(n-i)))初始化:全部初始化为1i......
  • 数据结构---二叉树
    二叉树的结构体:左右子树指针(Tree*) 值(int)typedefstructTree{chardata;structTree*lchild,*rchild;}*BiTree;二叉树的先序创建BiTreeCreate(......
  • #yyds干货盘点# LeetCode 腾讯精选练习 50 题:合并两个有序链表
    题目:将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例1:输入:l1=[1,2,4],l2=[1,3,4]输出:[1,1,2,3,4,4]示例2:......
  • 局部反转链表
    给你单链表的头指针head和两个整数 left和right,其中 left<=right。请你反转从位置left到位置right的链表节点,返回反转后的链表。publicListNodere......
  • 力扣OJ(601-800)
    目录​​621.任务调度器​​​​624.数组列表中的最大距离​​​​625.最小因式分解​​​​630.课程表III​​​​634.寻找数组的错位排列​​​​643.子数组最大平......
  • 2022.10.20-C 二叉树
    题意有一颗二叉树,满足一个结点要么是叶子结点,要么有两个儿子。同时,不存在一个叶子结点,使得它到根的路径上经过了\(\gem\)条向左的边。(左右子树有区别)对于\(1\lek\l......