※ 引述《JIWP (神楽めあ的錢包)》之銘言：
: 114. Flatten Binary Tree to Linked List
: 給一個binary tree，請將這顆binary tree變成以下形式
: 左子樹永遠是null，右子樹則依照原本tree pre-order去排列
: Follow up 請問你可以用o(1)的空間嗎
void flatten(struct TreeNode* root){
if(!root) return;
struct TreeNode* tmp = NULL;
flatten(root->left);
flatten(root->right);
if(!root->left)
return;
tmp = root->right;
root->right = root->left;
root->left = NULL;
while(root->right)
root = root->right;
root->right = tmp;
}
in-place好難
想法是後序遞迴
走到leaf的老爸P
tmp存P的右子樹
P的右邊指到P的左子樹
*然後P一直往右邊走直到下一個是NULL的P'時候再把tmp接到P'的右邊
處理完root的左子樹 右子樹 最後就處理root本身
但是加上*的這一步之後感覺就不是O(n)時間了
遞迴好難