Re: [閒聊] 每日leetcode

[NCKUEECS (小惠我婆)]

※ 引述《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)時間了

遞迴好難

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.143.2.62 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1709358737.A.C04.html
推 JIWP: 大師別卷了
→ NCKUEECS: 我通常都只挑easy寫:)
推 HGK: 大師
推 JIWP: 我的那個解法也是in place
→ NCKUEECS: 我說錯了 是o(1)空間 但時間就爛了 我不會算複雜度D:
推 DJYOSHITAKA: 大濕