🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 关注专栏： 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬 

二叉树一般使用链表进行存储，下面就来看一道二叉树转换为单链表的题目。

一、题目描述

给定二叉树的根结点 root ，请将它展开为一个单链表，展开规则如下所示：

（1）展开后的单链表应该同样使用 TreeNode；

（2）right 子指针指向链表中下一个结点，而左子指针始终为 null；

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

提示：

树中结点数在范围 [0, 2000] 内

-100 <= Node.val <= 100

二、测试样例

​ 图1 二叉树展开图

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

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

在上图中，二叉树展开后的单链表是「先序遍历」的顺序，注意：别忘记将节点的左指针赋值为空。

三、算法思路

本题主要考查「先序遍历」，在「先序遍历」过程中，将右指针指向下一个「先序遍历」节点，左子树访问完成后，将左指针赋值为空，一直到「先序遍历」完成。

四、代码实现

代码如下所示：

#include <iostream>

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) {}
};

class Solution {
public:
    void flatten(TreeNode* root) {
        if(!root) return;
        if(!root->left && !root->right) return;

        TreeNode* right = root->right;

        if(root->left) { // left 
            root->right = root->left;
            flatten(root->left);

            TreeNode* tmp = root;
            while(tmp->right) {
                tmp = tmp->right;
            }
            tmp->right = right;
        } else {
            root->right = right;
        }
        
        root->left = nullptr;
        flatten(right);
    }
};

int main()
{
    cout << "Hello world!" << endl;
    return 0;
}

​ 图2 通过截图 

五、复杂度分析

5.1 时间复杂度

时间复杂度：O(n)，其中，n 为二叉树节点个数，在上述算法中，需要访问二叉树所有节点，所以时间复杂度为 O(n)。

5.2 空间复杂度

空间复杂度：O(n)，其中，n 为二叉树节点个数，在上述算法中，递归访问过程中会使用栈进行存储，最大的空间复杂度为单支的二叉树，所以空间复杂度为 O(n)。

六、总结

本题主要在于「先序遍历」算法，「先序遍历」过程中转换指针的指向即可，注意：需要先访问过左子树的情况下，才将左指针赋值为空。

🎈 感觉有帮助记得「一键三连」支持下哦！有问题可在评论区留言💬，感谢大家的一路支持！🤞猿哥将持续输出「优质文章」回馈大家！🤞🌹🌹🌹🌹🌹🌹🤞

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 关注专栏： 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬