我恨指标，指标到底是三小
114. Flatten Binary Tree to Linked List
给一个binary tree，请将这颗binary tree变成以下形式
左子树永远是null，右子树则依照原本tree pre-order去排列
Follow up 请问你可以用o(1)的空间吗
思路 :
可以选择dfs并用array去记录每个node，接着慢慢把它串起来
不过这样空间就不是o(1)了
有兴趣可以自己去想看看o(1)的解法
c code
struct TreeNode* dfs(struct TreeNode* node,struct TreeNode* link){
if (node==NULL){
return NULL;
}
struct TreeNode* right,*left,*temp;
right=node->right;
left=node->left;
link->left=NULL;
link->right=node;
if (left==NULL && right==NULL){
return node;
}
temp=dfs(left,node);
if (right==NULL){
return temp;
}
if (left==NULL){
return dfs(right,node);
}
return dfs(right,temp);
}
void flatten(struct TreeNode* root) {
if (root==NULL){
return ;
}
struct TreeNode* right=root->right,*temp;
temp=dfs(root->left,root);
if (temp==NULL){
dfs(right,root); //记得要用right而不是root->right
}else{
dfs(right,temp);
}
}