作者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/cn.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