leetcode114：二叉树展开为链表

题目链接

leetcode

题目描述

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

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
using namespace std;

// 二叉树结点的定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

const int NULL_NODE = -101;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) {
        cout << endl;
        return;
    }

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    前序遍历一遍，然后将树转换为链表。

    时间复杂度：O(n)
        其中 n 是二叉树的结点数。
        前序遍历，时间复杂度是 O(n)。
        前序遍历之后，对每个结点更新左右子结点的信息，时间复杂度是 O(n)。
    空间复杂度：O(n)
        取决于栈（递归调用栈或迭代中使用的栈），存储前序遍历结果的数组大小。
        栈内的元素个数不会超过 n，数组中的元素个数是 n。
*/
// 递归实现
class Solution_0 {
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> res;

        preorderTraverse(root, res); // 前序遍历

        // 将树转换为链表
        for (int i = 1; i < res.size(); i++) {
            TreeNode *prev = res.at(i-1), *cur = res.at(i);
            prev->left = nullptr;
            prev->right = cur;
        }
    }

    void preorderTraverse(TreeNode* root, vector<TreeNode*>& res) {
        if (root != nullptr) {
            res.push_back(root);
            preorderTraverse(root->left, res);
            preorderTraverse(root->right, res);
        }
    }
};

// 迭代实现
class Solution_1 {
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> res;
        stack<TreeNode*> stk;
        TreeNode* node = root;

        // 前序遍历
        while (node != nullptr || !stk.empty()) {
            while (node != nullptr) {
                res.push_back(node);
                stk.push(node);
                node = node->left;
            }
            node = stk.top(); stk.pop();
            node = node->right;
        }

        // 将树转换为链表
        for (int i = 1; i < res.size(); i++) {
            TreeNode *prev = res.at(i-1), *cur = res.at(i);
            prev->left = nullptr;
            prev->right = cur;
        }
    }
};

/*
    前序遍历和展开同步进行

    每次从栈内弹出一个结点作为当前访问的结点，获得该结点的子结点。
    若子结点不为空，则依次将右子结点和左子结点压入栈内（注意入栈顺序）。

    时间复杂度：O(n)
    空间复杂度：O(n)
*/
class Solution_2 {
public:
    void flatten(TreeNode* root) {
        if (root == nullptr) {
            return;
        }

        stack<TreeNode*> stk;
        stk.push(root);
        TreeNode *prev = nullptr;

        while (!stk.empty()) {
            TreeNode *cur = stk.top(); stk.pop();
            if (prev != nullptr) {
                prev->left = nullptr;
                prev->right = cur;
            }
            if (cur->right != nullptr) {
                stk.push(cur->right);
            }
            if (cur->left != nullptr) {
                stk.push(cur->left);
            }
            prev = cur;
        }
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

// 辅助函数：打印二维数组
void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<vector<int>> root_cases = {
        {1,2,5,3,4,NULL_NODE,6},
        {},
        {0},
    };

    for (const auto& nums : root_cases) {
        cout << "Input: ";
        printArray(nums);

        // 创建二叉树
        TreeNode* root = createTree(nums);
        solution.flatten(root);
        cout << "Output: ";
        levelOrderTraversal(root);

        // 释放内存
        deleteTree(root);
    }

    return 0;
}