LeetCodehot100 力扣热题100 二叉树展开为链表

代码思路

目标：

将二叉树展平（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;  // 将前一个节点的左指针置为NULLprev->right = curr;    // 将前一个节点的右指针指向当前节点}}// preorderTraversal函数：前序遍历二叉树，并将每个节点加入到vector l中void preorderTraversal(TreeNode* root, vector<TreeNode*> &l) {if (root != NULL) {  // 如果当前节点不为空l.push_back(root);  // 将当前节点加入到vector lpreorderTraversal(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)（如果树是平衡的）。