题目描述
给你二叉树的根结点 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];
}
}
};