LeetCode第114题：二叉树展开为链表
2024-09-24 21:00:13
问题描述
给定一个二叉树，原地将它展开为链表。
例如，给定二叉树
1
/ \
2 5
/ \ \
3 4 6
将其展开为：
1
\
2
\
3
\
4
\
5
\
6
解题思路
二叉树的一些算法题都可以使用递归来解决，这道题也不例外。
首先对空指针应该直接返回。
然后递归将左子树展开为链表
1
/ \
2 5
\ \
3 6
\
4
再递归将右子树展开为链表
1
/ \
2 5
\ \
3 6
\
4
再然后暂存右子树，将左子树链接到根节点右孩子上，切记左孩子要置空！
1 5
\ \
2 6
\
3
\
4
随后找到当前树的最右孩子，将刚才暂存的右子树链接到右孩子上，结束。
1
\
2
\
3
\
4
\
5
\
6
我在做的时候也有疑问，要不要判断根节点的左子树是否为空呢？
其实并不需要，再接下来找最右孩子时，其实已经考虑到了这种情况。
C++代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void flatten(TreeNode* root) {
if(root==nullptr)
return;
//展开左子树为链表
if(root->left!=nullptr)
flatten(root->left);
//展开右子树为链表
if(root->right!=nullptr)
flatten(root->right);
//暂存右链表
TreeNode* temp=root->right;
//将左链表链接到根节点右孩子
root->right=root->left;
root->left=nullptr;
//随后将右链表链接到左链表最右孩子
TreeNode* mostRight=root;
while(mostRight->right!=nullptr){
mostRight=mostRight->right;
}
mostRight->right=temp;
return;
}
};
运行结果
最新文章
- MFC---给按钮加上快捷键
- github:如何获取项目源代码
- Hive UDF 实验1
- A script job for rebuild DB in AX 2012
- ZigBee HA示例程序分析
- C# 静态类和非静态类的区别
- centos6.5安装gcc6.1等c++环境
- Myeclipse中如何修改Tomcat的端口号
- 使用JS意识到自己主动提交表单
- kvm克隆
- .net core 2.x - 发布到IIS
- mybatis 一对一关联 association 返回空值
- 2017蓝桥杯 省赛D题(方格分割)
- 201621123002《JAVA程序设计》第四周学习总结
- px-pt-dp-rem像素单位的换算问题
- Beta阶段——第4篇 Scrum 冲刺博客
- mycat配置安装测试
- springboot 碰到的问题
- Iterator 和 Iterable 区别和联系
- 信息增益(Information Gain)（转）