作者ICECOCA (unknow)
看板C_and_CPP
標題[問題]leetcode Populating Next Right Pointers
時間Wed Feb 27 20:40:01 2019
開發平台(Platform): (Ex: Win10, Linux, ...)
編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出)
額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
問題(Question)：
leetcode #117. Populating Next Right Pointers in Each Node II
https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
餵入的資料(Input)：
這是leetcode #117 submission之後的測項
{"$id":"1","left":{"$id":"2","left":null,"next":null,"right":null,"val":-7},"next":null,"right":{"$id":"3","left":{"$id":"4","left":null,"next":null,"right":{"$id":"5","left":null,"next":null,"right":null,"val":8},"val":-1},"next":null,"right":{"$id":"6","left":{"$id":"7","left":null,"next":null,"right":null,"val":-9},"next":null,"right":null,"val":-7},"val":9},"val":-1}
預期的正確結果(Expected Output)：
這是測項預期的結果(但我認為是錯的(雖然不太可能...))
{"$id":"1","left":{"$id":"2","left":null,"next":{"$id":"3","left":{"$id":"4","left":null,"next":{"$id":"7","left":{"$ref":"6"},"next":null,"right":null,"val":-7},"right":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":-9},"right":null,"val":8},"val":-1},"next":null,"right":{"$ref":"7"},"val":9},"right":null,"val":-7},"next":null,"right":{"$ref":"3"},"val":-1}
錯誤結果(Wrong Output)：
程式碼(Code)：(請善用置底文網頁, 記得排版，禁止使用圖檔)
補充說明(Supplement)：
小弟問題有兩個
1. 是 我認為該tesecase 結果是錯的，因為node4 照原本的tree和題目要求
node4->next 應該是 node6, 但是預期結果卻是給出node4->next 為 node7
雖然我認為leetcode錯的機會比較小XD，想問一下有人有刷過這題經驗幫忙再
submmit 看看嗎?
2. tree的圖形是 人工畫出來的，另外想請問根據這種輸入
有比較方面畫出tree的圖形的網頁或是tool嗎?
我是用C++ DFS 做這題
https://glot.io/snippets/f9vo8sf9sp
class Solution {public:
Node* askNext(Node* root) {
if(!root) return nullptr;
if(root->next==nullptr){
if(root->left){
root->left->next = root->right;
return root->left;
}
return root->right;
}
Node* chilSibling = askNext(root->next);
if(root->right){
root->right->next = chilSibling;
chilSibling = root->right;
}
if(root->left){
root->left->next = chilSibling;
chilSibling = root->left;
}
return chilSibling;
}
void dfsDown(Node* root) {
if(!root) return;
askNext(root);
if(root->left)
return dfsDown(root->left);
else
return dfsDown(root->right);
}
Node* connect(Node* root) {
dfsDown(root);
return root;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.34.229.162
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1551271207.A.0F2.html
※ 編輯: ICECOCA (114.34.229.162), 02/27/2019 20:44:20
※ 編輯: ICECOCA (114.34.229.162), 02/27/2019 20:45:00
1F：→ Feis: 我結果跟 LeetCode 一樣，試寫了一下會過 02/27 22:37
2F：→ firejox: 他網頁不就可以顯示tree圖 02/28 11:22
3F：→ ICECOCA: 感謝1F大, 我再看看 03/01 14:07
4F：→ ICECOCA: @2F, 如果是[1,2,null,3] 這種陣列input 才有的樣子 03/01 14:08