114. 二叉树展开为链表
2023-04-18 16:11:57 时间
给你二叉树的根结点 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:
思路:
- 将左子树插入到右子树的地方
- 将原来的右子树接到左子树的最右边节点
- 考虑新的右子树的根节点,一直重复上边的过程,直到新的右子树为 null
1
/
2 5
/
3 4 6
//将 1 的左子树插入到右子树的地方
1
2 5
/
3 4 6
//将原来的右子树接到左子树的最右边节点
1
2
/
3 4
5
6
//将 2 的左子树插入到右子树的地方
1
2
3 4
5
6
//将原来的右子树接到左子树的最右边节点
1
2
3
4
5
6
......
代码:
public void flatten(TreeNode root) {
TreeNode curr=root;
while (curr!=null){
if (curr.left==null){
curr=curr.right;
}else {
TreeNode leftRight=curr.left;
//找到左孩子最右边结点,将有孩子挂上去
while (leftRight.right!=null){
leftRight=leftRight.right;
}
leftRight.right=curr.right;
curr.right=curr.left;
curr.left=null;
curr=curr.right;
}
}
}
相关文章
- condition_variable介绍
- 论“GPL就是给软件开发者们准备的坑”
- 如何避免云计算供应商的锁定
- SaaS布局优势凸显 腾讯To B业务加速升级
- 阿里云贾扬清:大数据+AI工程化 把数据真正“用”起来
- 了解3GPP 5G版本及每个版本功能
- Canalys:一季度美国云基础设施支出猛增29%
- 亲友相聚时刻WiFi密码只能口口相传?不安全!
- 回归实体:金融科技的下一站
- 部署混合云环境的五大挑战
- 家装产业化,一次真正意义上的新生
- 数字化,家装行业的蝶变之道
- 元宇宙:区块链时代的新名字
- 数字化转型的迷思与SaaS的机会
- 中国移动10年老用户,将享受4大特权,网友:让联通脸往哪搁
- 二分搜索技术
- 春节宅家玩乐不发愁 WiFi这样调才流畅
- 云数据隐私:将密钥放在哪里?
- 2020年全球频谱拍卖总价值达275亿美元
- VMware为现代化分布式企业提供更高安全性和业务韧性