Leetcode No.114 二叉树展开为链表(DFS)
2023-03-20 14:56:09 时间
一、题目描述
给你二叉树的根结点 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
二、解题思路
将二叉树展开为单链表之后,单链表中的节点顺序即为二叉树的前序遍历访问各节点的顺序。因此,可以对二叉树进行前序遍历,获得各节点被访问到的顺序。由于将二叉树展开为链表之后会破坏二叉树的结构,因此在前序遍历结束之后更新每个节点的左右子节点的信息,将二叉树展开为单链表。
对二叉树的前序遍历不熟悉的读者请自行练习「144. 二叉树的前序遍历」。
前序遍历可以通过递归或者迭代的方式实现。以下代码通过递归实现前序遍历。
三、代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list=new ArrayList<>();
preTravel(root,list);
TreeNode pre,cur;
for(int i=1;i<list.size();i++){
pre=list.get(i-1);
cur=list.get(i);
pre.right=cur;
pre.left=null;
}
}
public void preTravel(TreeNode root, List<TreeNode> list){
if(root!=null){
list.add(root);
preTravel(root.left,list);
preTravel(root.right,list);
}
return;
}
}
四、复杂度分析
时间复杂度:O(n),其中 n 是二叉树的节点数。前序遍历的时间复杂度是 O(n),前序遍历之后,需要对每个节点更新左右子节点的信息,时间复杂度也是 O(n)。
空间复杂度:O(n),其中 n 是二叉树的节点数。空间复杂度取决于栈(递归调用栈或者迭代中显性使用的栈)和存储前序遍历结果的列表的大小,栈内的元素个数不会超过 n,前序遍历列表中的元素个数是 n。
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十