网站后台更新前台更新不,微信企业号,烟台专业网站制作公司,微擎商城代码思路 目标#xff1a;
将二叉树展平#xff08;flatten#xff09;为一个单链表。展平后的链表应该按照前序遍历的顺序排列节点#xff0c;即#xff1a;
• 节点的左子树指针设置为 nullptr。
• 节点的右子树指针指向下一个节点。 代码注释及思路 class Solution… 代码思路 目标
将二叉树展平flatten为一个单链表。展平后的链表应该按照前序遍历的顺序排列节点即
• 节点的左子树指针设置为 nullptr。
• 节点的右子树指针指向下一个节点。 代码注释及思路 class Solution {public:// flatten函数将二叉树转化为链表void flatten(TreeNode* root) {vectorTreeNode* 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, vectorTreeNode* 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::vectorint 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::vectorint v {10, 20, 30, 40};
std::cout v[5] std::endl; // 未定义行为可能导致程序崩溃或异常
• at(i)比 operator[] 更安全因为它会进行边界检查并抛出异常。
• operator[]更加高效因为没有进行边界检查但使用不当会导致程序崩溃或产生不可预料的行为。 哪个更好
• 如果你确定索引是有效的或者你对代码的安全性非常关注使用 operator[] 会更高效。
• 如果你更关心代码的安全性尤其是在你不确定索引是否有效的情况下使用 at() 更加可靠。
详细思路
1. 前序遍历
• 在 flatten 函数中首先调用 preorderTraversal 对二叉树进行前序遍历。前序遍历的顺序是根节点 → 左子树 → 右子树。
• 在 preorderTraversal 函数中当访问一个节点时将它加入到一个 vectorTreeNode*即 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)如果树是平衡的。
