我恨指標，指標到底是三小
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);
}
}