【C++】每日一题 114 二叉树展开为链表

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

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

#include <iostream>
#include <queue>

using namespace std;

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

void queuex(TreeNode* root, queue<TreeNode*>& qt) {
    if(root == NULL) {
        return;
    }
    qt.push(root);
    queuex(root->left, qt);
    queuex(root->right, qt);
}

void flatten(TreeNode* root) {
    if(root == NULL) {
        return;
    }
    queue<TreeNode*> qt;
    queuex(root, qt);
    TreeNode* next = root;
    qt.pop(); // pop the root node
    while(!qt.empty()) {
        next->left = NULL;
        next->right = qt.front();
        next = next->right;
        qt.pop();
    }
}

考虑使用原地算法（O(1) 额外空间）展开这棵树

#include <iostream>

using namespace std;

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

void flatten(TreeNode* root) {
    while (root != nullptr) {
        if (root->left != nullptr) {
            // 找到左子树的最右节点
            TreeNode* pre = root->left;
            while (pre->right != nullptr) {
                pre = pre->right;
            }
            // 将根节点的右子树接到左子树的最右节点上
            pre->right = root->right;
            // 将整个左子树移到右子树位置
            root->right = root->left;
            root->left = nullptr;
        }
        // 处理下一个节点
        root = root->right;
    }
}

// 辅助函数，中序遍历打印树
void inorderPrint(TreeNode* root) {
    if (root == nullptr) return;
    inorderPrint(root->left);
    cout << root->val << " ";
    inorderPrint(root->right);
}

int main() {
    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);

    cout << "Original tree:" << endl;
    inorderPrint(root);
    cout << endl;

    flatten(root);

    cout << "Flattened tree:" << endl;
    inorderPrint(root);
    cout << endl;

    return 0;
}

利用 Morris 遍历算法。Morris 遍历算法是一种遍历二叉树的方法，其核心思想是通过线索化二叉树的空闲指针，使得可以在不使用额外空间的情况下遍历整个二叉树
先检查每个节点的左子树是否为空。如果不为空，则找到左子树的最右节点（即左子树中最右边的节点），然后将根节点的右子树接到左子树的最右节点上，接着将整个左子树移到根节点的右子树位置。最后，处理下一个节点，直到遍历完整个二叉树。