题目描述

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

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

出处

思路

先序遍历，维护链指针。

代码

class Solution {
public:
    void visit(TreeNode* root,vector<TreeNode*>& queue){
        queue.push_back(root);
        if(root->left) visit(root->left,queue);
        if(root->right) visit(root->right,queue);
    }
    void flatten(TreeNode* root) {
        if(!root) return;
        vector<TreeNode*> queue;
        visit(root,queue);
        for(int i=0;i<queue.size()-1;i++){
            queue[i]->left=nullptr;
            queue[i]->right=queue[i+1];
        }
    }
};