原题链接🔗：二叉树展开为链表
难度：中等⭐️⭐️

题目

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null。

展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

提示：

树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

题解

二叉树前序遍历

二叉树的前序遍历是一种树遍历算法，其遍历顺序为：先访问根节点，然后遍历左子树，最后遍历右子树。前序遍历通常使用递归或栈来实现。以下是前序遍历的一般步骤：

• 访问根节点。
• 前序遍历左子树。
• 前序遍历右子树。
• 如果使用递归实现，可以按照以下伪代码进行：

function 前序遍历(node):
    if node is not null:
        visit(node)  // 访问当前节点
        前序遍历(node.left)  // 递归遍历左子树
        前序遍历(node.right)  // 递归遍历右子树

前序遍历法

1. 解题思路：

LeetCode上的“二叉树展开为链表”问题要求我们通过前序遍历的方式，将给定的二叉树转换为一个链表。前序遍历的顺序是先访问根节点，然后是左子树，最后是右子树。以下是使用前序遍历法解题的步骤和思路：

• 定义问题：给定一个二叉树的根节点root，我们需要将这个树转换为一个链表，其中树的左子节点将成为链表的前序部分，右子节点将被忽略。

• 递归调用：使用递归函数flatten，首先对左子树进行操作，然后对右子树进行操作。递归的终止条件是节点为空。

  • 在 flatten 函数内部，我们定义了一个 vector<TreeNode*> 类型的变量 l，用来存储前序遍历的结果。
  • 调用 preorderTraversal 函数，传入 root 和 l 作为参数，进行前序遍历，并将遍历的结果存储在 l 中。
  • 计算 l 的大小，即二叉树中节点的数量，存储在变量 n 中。
  • 使用一个循环，从 1 到 n-1（不包括 n），对 l 中的节点进行迭代。在每次迭代中：
    • 使用 l.at(i - 1) 获取当前节点的前一个节点，赋值给 prev。
    • 使用 l.at(i) 获取当前节点，赋值给 curr。
    • 将 prev 的左子节点设置为 nullptr，表示它没有左子节点。
    • 将 prev 的右子节点设置为 curr，将当前节点链接到前一个节点的右边。
  • preorderTraversal 函数是一个递归函数，用于执行前序遍历。如果 root 不为 NULL：
    • 将 root 添加到 l 中。
    • 递归调用 preorderTraversal 函数，分别对 root 的左子节点和右子节点进行前序遍历。

• 递归返回：递归返回，直到根节点被处理，此时整个树已经被转换为链表。

• 测试和验证：编写测试代码来验证算法的正确性。

2. 复杂度：时间复杂度O(n)，空间复杂度O(n)。
3. c++ demo：

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> l;
        preorderTraversal(root, 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;
            prev->right = curr;
        }
    }

    void preorderTraversal(TreeNode* root, vector<TreeNode*>& l) {
        if (root != NULL) {
            l.push_back(root);
            preorderTraversal(root->left, l);
            preorderTraversal(root->right, l);
        }
    }
};


int main() {
    // 构建一个示例二叉树
    //       1
    //      / \
    //     2   5
    //    / \   \
    //   3   4   6
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(5);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(6);

    // 调用函数展开二叉树
    Solution solution;
    solution.flatten(root);

    // 打印展开后的链表
    TreeNode* current = root;
    while (current) {
        std::cout << current->val << " ";
        current = current->right;
    }

    return 0;
}

• 输出结果：

1 2 3 4 5 6

4. 代码仓库地址：flatten