二叉树展开为链表
解题思路：
- 先进行先序遍历；
- 再用先序遍历的结果构造链表；
复杂度：
- 时间复杂度：O(n)，其中 n 是二叉树的节点数；前序遍历的时间复杂度是 O(n)，前序遍历之后，需要对每个节点更新左右子节点的信息，时间复杂度也是 O(n)；
- 空间复杂度：O(n)，其中 n 是二叉树的节点数；空间复杂度取决于栈（递归调用栈或者迭代中显性使用的栈）和存储前序遍历结果的列表的大小，栈内的元素个数不会超过 n，前序遍历列表中的元素个数是 n；
代码实现：
var flatten = function (root) {
let list = []
// 先序遍历
preTravese(root, list)
// 拿先序遍历的结果构造二叉树
for (let i = 1; i < list.length; i++) {
const prev = list[i - 1] // prev 就是root
const cur = list[i]
prev.left = null
prev.right = cur
}
};
function preTravese(root, list) {
if (root !== null) {
list.push(root)
preTravese(root.left, list)
preTravese(root.right, list)
}
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 160. 相交链表
上一篇
评论
