[114] Flatten Binary Tree to Linked List

想來又要大肆的自我厭惡一番了 Orz

以為寫的出來所以掙扎很久，各種卡住TOT

看解答之後才大驚，啊原來是這樣嗎Orz 我沒有天份啊啊啊啊啊

struct TreeNode* inner(struct TreeNode* root ){

if (root == NULL)

return root;

if (root->left== NULL && root->right == NULL)

return root;

if (root->left==NULL)

return inner(root->right);

if (root->right == NULL)

{

root->right = root->left;

root->left = NULL;

return inner(root->right);

}

struct TreeNode* ptr = root->right;

root->right = root->left;

root->left=NULL;

struct TreeNode* newRoot = inner(root->right);

newRoot->right = ptr;

return inner(ptr);

}

void flatten(struct TreeNode* root){

inner(root);

}

也看了另一種解法，似乎比較貼近我原本想寫的寫法，但是難道說！！！

原來要先從右邊把尾巴的pointer 存起來是嗎Orz

天啊我好沒有天份啊啊啊啊啊啊啊啊（跌坐在地）

void inner(struct TreeNode* root,struct TreeNode **ptr ){

if (root ==NULL)

return;

inner(root->right, ptr);

inner(root->left, ptr);

root->right = *ptr;

root->left=NULL;

*ptr = root;

}

void flatten(struct TreeNode* root){

struct TreeNode** ptr = malloc (sizeof (struct TreeNode*) );

*ptr = NULL;

inner(root, ptr);

free (ptr);

}