[問題]leetcode Populating Next Right Pointers

看板C_and_CPP (C/C++)作者ICECOCA (unknow)時間7年前 (2019/02/27 20:40)推噓0(0推 0噓 4→)

留言4則, 3人參與討論串1/1

開發平台(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://www.ptt.cc/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