Leetcode—114. 二叉树展开为链表【中等】

2023每日刷题（九十八）

Leetcode—114. 二叉树展开为链表

在这里插入图片描述

Morris-like算法思想

可以发现展开的顺序其实就是二叉树的先序遍历。算法和 94 题中序遍历的 Morris 算法有些神似，我们需要两步完成这道题。

将左子树插入到右子树的地方
将原来的右子树接到左子树的最右边节点
考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null

在这里插入图片描述

实现代码

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        while(root != nullptr) {
            if(root->left == nullptr) {
                root = root->right;
            } else {
                TreeNode* pre = root->left;
                // pre指向root左子树最右结点
                while(pre->right != nullptr) {
                    pre = pre->right;
                }
                pre->right = root->right;
                root->right = root->left;
                root->left = nullptr;
                root = root->right;
            }
        }
    }
};

运行结果

在这里插入图片描述

前序遍历dfs算法思想

将二叉树展开为单链表之后，单链表中的节点顺序即为二叉树的前序遍历访问各节点的顺序。因此，可以对二叉树进行前序遍历，获得各节点被访问到的顺序。由于将二叉树展开为链表之后会破坏二叉树的结构，因此在前序遍历结束之后更新每个节点的左右子节点的信息，将二叉树展开为单链表。

实现代码

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> ans;
        // 前序遍历用ans记录顺序
        function<void(TreeNode*)> dfs = [&](TreeNode* root) {
            if(root == nullptr) {
                return;
            }
            ans.push_back(root);
            dfs(root->left);
            dfs(root->right);
        };
        dfs(root);
        int n = ans.size();
        for(int i = 1; i < n; i++) {
            TreeNode* pre = ans.at(i - 1);
            TreeNode* cur = ans.at(i);
            pre->left = nullptr;
            pre->right = cur;
        }
    }
};