二叉树展开为链表的前序遍历方法

"19_二叉树展开为链表.pdf" 二叉树展开为链表是一种数据结构转换问题，目标是将一棵二叉树按照先序遍历的顺序转换成一个单链表，其中链表的节点是二叉树节点，且每个节点的右子指针指向链表中的下一个节点，左子指针始终为null。 在示例1中，给定的二叉树是 `[1,2,5,3,4,null,6]`，展开后的链表应该是 `[1,null,2,null,3,null,4,null,5,null,6]`。在示例2中，若输入的二叉树为空，即 `root=[]`，则输出的链表也应该为空。 解决这个问题通常有两种方法，都是基于前序遍历的思想： 方法1：前序遍历 1. 首先，我们进行前序遍历，将二叉树的所有节点存储在一个列表（List）中，这样得到的顺序就是按照先序遍历的顺序。 2. 前序遍历结束后，遍历这个列表，对于列表中的每个节点（除了第一个），将其左子节点设为null，右子节点设为下一个节点。这样就形成了一个单链表。 在Java实现中，我们可以定义一个Solution类，包含两个方法：`flatten` 和 `preorderTraversal`。`flatten` 方法负责整个过程，它调用 `preorderTraversal` 进行前序遍历，并更新节点的子节点信息。时间复杂度为O(n)，因为前序遍历和更新节点信息各需要O(n)的时间。 方法2： 尽管题目没有给出第二种方法的具体代码，但通常第二种方法会尝试在遍历过程中直接进行转换，避免额外的列表存储。这可能涉及递归或迭代的前序遍历，在遍历的过程中修改树结构，使其变为链表。这种方法同样保持了O(n)的时间复杂度，但空间复杂度可能更低，因为它不需要额外的空间来存储所有节点。 总结来说，二叉树展开为链表的关键在于利用先序遍历的特性，确保链表的顺序正确，并在遍历过程中重新构建节点的连接关系。这两种方法都提供了有效且高效的解决方案。