Re: [闲聊] 每日leetcode

楼主: NCKUEECS (小惠我婆)   2024-03-02 13:52:15
※ 引述《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)时间了
递回好难
作者: JIWP (JIWP)   2024-03-02 13:53:00
大师别卷了
楼主: NCKUEECS (小惠我婆)   2024-03-02 13:53:00
我通常都只挑easy写:)
作者: HGK (HGK)   2024-03-02 13:54:00
大师
作者: JIWP (JIWP)   2024-03-02 13:55:00
我的那个解法也是in place
楼主: NCKUEECS (小惠我婆)   2024-03-02 13:56:00
我说错了 是o(1)空间 但时间就烂了 我不会算复杂度D:
作者: DJYOSHITAKA (Evans)   2024-03-02 14:17:00
大湿

Links booklink

Contact Us: admin [ a t ] ucptt.com