DEV Community
·
Leetcode - 114. 将二叉树扁平化为链表
💡
原文英文，约600词，阅读约需2分钟。
📝
内容提要
本文讨论了如何使用递归方法将二叉树原地扁平化为链表。通过先扁平化左子树，再扁平化右子树，连接左右子树，最终形成链表结构。代码示例展示了尾节点的查找和空值检查，时间复杂度为O(n)，空间复杂度为O(h)。
🎯
关键要点
- 本文讨论如何使用递归方法将二叉树原地扁平化为链表。
- 使用深度优先搜索递归方法，先扁平化左子树，再扁平化右子树。
- 连接扁平化的左子树和右子树，形成链表结构。
- 代码示例展示了尾节点的查找和空值检查。
- 时间复杂度为O(n)，空间复杂度为O(h)。
- 在扁平化过程中，必须小心处理空值检查。
- 此方法在原地修改树，空间复杂度与树的高度有关。
- 递归方法与人类思维方式相似，易于理解和实现。
❓
延伸问答
如何将二叉树扁平化为链表？
使用递归方法，先扁平化左子树，再扁平化右子树，最后连接左右子树形成链表。
扁平化二叉树的时间和空间复杂度是多少？
时间复杂度为O(n)，空间复杂度为O(h)，其中h是树的高度。
在扁平化过程中需要注意什么？
必须小心处理空值检查，以避免错误。
如何查找扁平化子树的尾节点？
通过递归遍历右子树，直到找到右子树的最右节点。
为什么要将左子树连接到右子树？
因为在链表结构中，节点只需要右指针，左指针应设置为null。
这个递归方法有什么优点？
该方法易于理解，符合人类思维方式，且实现简洁。
➡️
