Re: [閒聊] 每日leetcode
我恨指標，指標到底是三小
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
推
03/01 21:44,
1年前
, 1F
03/01 21:44, 1F
推
03/01 21:45,
1年前
, 2F
03/01 21:45, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 13 之 1548 篇)：