※ 引述《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)时间了
递回好难