Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

我恨指標，指標到底是三小

114. Flatten Binary Tree to Linked List

給一個binary tree，請將這顆binary tree變成以下形式

左子樹永遠是null，右子樹則依照原本tree pre-order去排列

Follow up 請問你可以用o(1)的空間嗎

思路 :

可以選擇dfs並用array去記錄每個node，接著慢慢把它串起來

不過這樣空間就不是o(1)了

有興趣可以自己去想看看o(1)的解法

c code

struct TreeNode* dfs(struct TreeNode* node,struct TreeNode* link){
    if (node==NULL){
        return NULL;
    }
    struct TreeNode* right,*left,*temp;
    right=node->right;
    left=node->left;
    link->left=NULL;
    link->right=node;
    if (left==NULL && right==NULL){
        return node;
    }
    temp=dfs(left,node);
    if (right==NULL){
        return temp;
    }
    if (left==NULL){
        return dfs(right,node);
    }
    return dfs(right,temp);

}

void flatten(struct TreeNode* root) {
    if (root==NULL){
        return ;
    }
    struct TreeNode* right=root->right,*temp;
    temp=dfs(root->left,root);
    if (temp==NULL){
        dfs(right,root); //記得要用right而不是root->right
    }else{
        dfs(right,temp);
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.6.22 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1709300615.A.A54.html
推 Che31128: 大師
推 HGK: 施