Re: [閒聊] 每日leetcode已回收
※ 引述《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
推
03/02 13:53,
1年前
, 1F
03/02 13:53, 1F
→
03/02 13:53,
1年前
, 2F
03/02 13:53, 2F
推
03/02 13:54,
1年前
, 3F
03/02 13:54, 3F
推
03/02 13:55,
1年前
, 4F
03/02 13:55, 4F
→
03/02 13:56,
1年前
, 5F
03/02 13:56, 5F
推
03/02 14:17,
1年前
, 6F
03/02 14:17, 6F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 14 之 1548 篇)：