代码思路
目标：
将二叉树展平（flatten）为一个单链表。展平后的链表应该按照前序遍历的顺序排列节点，即：
• 节点的左子树指针设置为 nullptr。
• 节点的右子树指针指向下一个节点。
代码注释及思路
class Solution {
public:
// flatten函数：将二叉树转化为链表
void flatten(TreeNode* root) {
vector<TreeNode*> l; // 用来存储前序遍历的节点
preorderTraversal(root, l); // 先进行前序遍历并将节点加入到l中
int n = l.size(); // 记录前序遍历中节点的个数
// 连接所有节点，使其形成链表
for (int i = 1; i < n; i++) {
TreeNode *prev = l.at(i - 1), *curr = l.at(i);
prev->left = nullptr; // 将前一个节点的左指针置为NULL
prev->right = curr; // 将前一个节点的右指针指向当前节点
}
}
// preorderTraversal函数：前序遍历二叉树，并将每个节点加入到vector l中
void preorderTraversal(TreeNode* root, vector<TreeNode*> &l) {
if (root != NULL) { // 如果当前节点不为空
l.push_back(root); // 将当前节点加入到vector l
preorderTraversal(root->left, l); // 递归遍历左子树
preorderTraversal(root->right, l); // 递归遍历右子树
}
}
};l.at(i - 1) 和 l[i - 1] 在大多数情况下会表现得很相似，但它们有一些关键的区别，主要体现在安全性和异常处理上。
1. l.at(i - 1)
• 安全性：at() 是 std::vector 的一个成员函数，它会检查你传入的索引是否越界。如果索引超出了有效范围，它会抛出一个 std::out_of_range 异常。
• 行为：如果你访问了一个无效索引（比如负数或者超出了 vector 的大小），at() 会立即抛出异常，从而帮助你捕捉潜在的错误。
std::vector<int> v = {10, 20, 30, 40};
try {
std::cout << v.at(5) << std::endl; // 抛出 std::out_of_range 异常
} catch (const std::out_of_range& e) {
std::cout << "Out of range: " << e.what() << std::endl; // 会打印异常信息
}
2. l[i - 1]
• 安全性：operator[] 是 std::vector 的索引访问方式，它不会做越界检查。如果你使用一个无效的索引，它不会抛出异常，而是会产生未定义行为，可能导致程序崩溃、访问到非法内存等问题。
• 行为：即使访问了一个超出范围的索引，它也不会报错，而是直接返回一个非法的内存位置。
std::vector<int> v = {10, 20, 30, 40};
std::cout << v[5] << std::endl; // 未定义行为，可能导致程序崩溃或异常
• at(i)：比 operator[] 更安全，因为它会进行边界检查并抛出异常。
• operator[]：更加高效，因为没有进行边界检查，但使用不当会导致程序崩溃或产生不可预料的行为。
哪个更好？
• 如果你确定索引是有效的，或者你对代码的安全性非常关注，使用 operator[] 会更高效。
• 如果你更关心代码的安全性，尤其是在你不确定索引是否有效的情况下，使用 at() 更加可靠。
详细思路
1. 前序遍历：
• 在 flatten 函数中，首先调用 preorderTraversal 对二叉树进行前序遍历。前序遍历的顺序是：根节点 → 左子树 → 右子树。
• 在 preorderTraversal 函数中，当访问一个节点时，将它加入到一个 vector<TreeNode*>（即 l）中。
• 递归进行左子树和右子树的遍历。
2. 重建链表：
• 在完成前序遍历后，l 中存储了按前序遍历顺序排列的所有节点。
• 接下来，遍历这个 l，并对每一对相邻节点（prev 和 curr）做以下操作：
• 将 prev 节点的左指针置为 nullptr。
• 将 prev 节点的右指针指向 curr 节点。
• 这样，我们将树的结构变为链表，且节点按照前序遍历顺序排列。
运行步骤
假设输入的二叉树如下：
1
/ \
2 5
/ \ \
3 4 6
1. 调用 flatten(root)，传入根节点 1。
2. 调用 preorderTraversal(root, l)，此时开始前序遍历：
• l = [1]（根节点 1）
• 遍历左子树，l = [1, 2]
• 遍历 2 的左子树，l = [1, 2, 3]
• 遍历 2 的右子树，l = [1, 2, 3, 4]
• 遍历右子树，l = [1, 2, 3, 4, 5]
• 遍历 5 的右子树，l = [1, 2, 3, 4, 5, 6]
3. 现在，l = [1, 2, 3, 4, 5, 6]，即按前序遍历顺序排列的节点。
4. 接着，连接这些节点：
• prev = 1, curr = 2 → 1->left = nullptr, 1->right = 2
• prev = 2, curr = 3 → 2->left = nullptr, 2->right = 3
• prev = 3, curr = 4 → 3->left = nullptr, 3->right = 4
• prev = 4, curr = 5 → 4->left = nullptr, 4->right = 5
• prev = 5, curr = 6 → 5->left = nullptr, 5->right = 6
最终的链表结构如下：
1 -> 2 -> 3 -> 4 -> 5 -> 6
复杂度分析
• 时间复杂度：O(n)，其中 n 是树中节点的数量。我们对树进行了一次前序遍历，遍历过程的时间复杂度是 O(n)。在重新连接节点时，也只需要遍历一次 l。
• 空间复杂度：O(n)，主要是用于存储前序遍历结果的 vector l，其大小为 n。递归栈的深度是树的高度，最坏情况下是 O(n)，最好的情况下是 O(log n)（如果树是平衡的）。
