leetcode 117
代码
#include <iostream>
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(NULL), right(NULL), next(NULL) {}
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
class Solution {
public:
void handle(Node* &last, Node* &p, Node* &nextStart) {
if (last) {
last->next = p;
}
if (!nextStart) {
nextStart = p;
}
last = p;
}
Node* connect(Node* root) {
if (!root) {
return nullptr;
}
Node *start = root;
while (start) {
Node *last = nullptr, *nextStart = nullptr;
for (Node *p = start; p != nullptr; p = p->next) {
if (p->left) {
handle(last, p->left, nextStart);
}
if (p->right) {
handle(last, p->right, nextStart);
}
}
start = nextStart;
}
return root;
}
};
int main(){
Node* n1 = new Node(1);
Node* n2 = new Node(2);
Node* n3 = new Node(3);
Node* n4 = new Node(4);
Node* n5 = new Node(5);
Node* n6 = new Node(6);
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;
n3->right = n6;
Solution s;
Node* res = new Node();
res = s.connect(n1);
return 0;
}
这个解法的优点是对空间占用比直接层序遍历更好。27行和29行会更新指针本身，而不仅是指针的指向对象的值。
gdb调试
c++ 知识点
Node *&、Node&和Node *之间的区别在于它们的类型和用法。
-
Node *&是一个引用的引用，表示一个指向指针的引用。这种引用的使用场景通常是为了能够修改指针本身的值，而不仅仅是修改指针所指向的对象的值。通过Node *&可以修改指针的指向，从而改变原始指针的值。 -
Node&是一个引用，表示对Node类型对象的引用。通过Node&可以直接访问和修改引用所指向的对象的成员变量。 -
Node *是一个指针，用于指向Node类型的对象。通过指针可以间接访问和修改指针所指向的对象的成员变量。
以下是一个示例，展示了Node *&、Node&和Node *之间的区别：
#include <iostream>
class Node {
public:
int data;
Node* next;
Node(int value) {
data = value;
next = nullptr;
}
};
void modifyPointer(Node *&ptr) {
ptr = new Node(20);
}
void modifyReference(Node &ref) {
ref.data = 30;
}
void modifyObject(Node *ptr) {
ptr->data = 40;
}
int main() {
Node* node1 = new Node(10);
// 使用 Node *& 修改指针本身的值
modifyPointer(node1);
std::cout << "Modified pointer: " << node1->data << std::endl;
// 使用 Node & 修改引用所指向的对象的值
modifyReference(*node1);
std::cout << "Modified reference: " << node1->data << std::endl;
// 使用 Node * 修改指针所指向的对象的值
modifyObject(node1);
std::cout << "Modified object: " << node1->data << std::endl;
delete node1;
return 0;
}
在上面的示例中，我们定义了一个Node类，它有两个成员变量data和next。我们还定义了三个函数modifyPointer、modifyReference和modifyObject来修改指针和对象的值。
在main函数中，我们首先创建了一个node1节点，并将其传递给modifyPointer函数。modifyPointer函数接受一个Node *&类型的参数，它修改了指针本身的值，将其指向一个新创建的Node对象。然后，我们打印出修改后的指针所指向的对象的值。
接下来，我们将node1节点传递给modifyReference函数。modifyReference函数接受一个Node &类型的参数，它修改了引用所指向的对象的值，将其data成员变量设置为30。然后，我们再次打印出修改后的对象的值。
最后，我们将node1节点传递给modifyObject函数。modifyObject函数接受一个Node *类型的参数，它修改了指针所指向的对象的值，将其data成员变量设置为40。然后，我们再次打印出修改后的对象的值。
输出结果应该是：
Modified pointer: 20
Modified reference: 30
Modified object: 40
这样，我们可以看到Node *&、Node&和Node *之间的区别。Node *&允许我们修改指针本身的值，Node &允许我们直接修改引用所指向的对象的值，而Node *只能通过指针间接访问和修改指针所指向的对象的值。
(gdb) b 22
Breakpoint 1 at 0x40089a: file leetcode117.cpp, line 22.
(gdb) b 30
Breakpoint 2 at 0x4008e0: file leetcode117.cpp, line 30.
(gdb) r
Starting program: /home/csapp/leetcode/leetcode117
warning: Error disabling address space randomization: Operation not permitted
Breakpoint 1, Solution::handle (this=0x7fff7657bd37, last=@0x7fff7657bd08: 0x0, p=@0x15d1018: 0x15d1040,
nextStart=@0x7fff7657bd00: 0x0) at leetcode117.cpp:23
23 if (last) {
Missing separate debuginfos, use: debuginfo-install glibc-2.17-326.el7_9.x86_64 libgcc-4.8.5-44.el7.x86_64 libstdc+±4.8.5-44.el7.x86_64
(gdb) p *last
Cannot access memory at address 0x0
(gdb) c
Continuing.
Breakpoint 2, Solution::handle (this=0x7fff7657bd37, last=@0x7fff7657bd08: 0x15d1040, p=@0x15d1018: 0x15d1040,
nextStart=@0x7fff7657bd00: 0x15d1040) at leetcode117.cpp:31
31 }
(gdb) p *last
$1 = {val = 2, left = 0x15d10a0, right = 0x15d10d0, next = 0x0}
(gdb) p *p
$2 = {val = 2, left = 0x15d10a0, right = 0x15d10d0, next = 0x0}
(gdb) p *nextStart
$3 = {val = 2, left = 0x15d10a0, right = 0x15d10d0, next = 0x0}
(gdb) c
Continuing.
Breakpoint 1, Solution::handle (this=0x7fff7657bd37, last=@0x7fff7657bd08: 0x15d1040, p=@0x15d1020: 0x15d1070,
nextStart=@0x7fff7657bd00: 0x15d1040) at leetcode117.cpp:23
23 if (last) {
(gdb) p *last
$4 = {val = 2, left = 0x15d10a0, right = 0x15d10d0, next = 0x0}
(gdb) p *p
$5 = {val = 3, left = 0x0, right = 0x15d1100, next = 0x0}
(gdb) p *nextStart
$6 = {val = 2, left = 0x15d10a0, right = 0x15d10d0, next = 0x0}
(gdb) c
Continuing.
Breakpoint 2, Solution::handle (this=0x7fff7657bd37, last=@0x7fff7657bd08: 0x15d1070, p=@0x15d1020: 0x15d1070,
nextStart=@0x7fff7657bd00: 0x15d1040) at leetcode117.cpp:31
31 }
(gdb) p *last
$7 = {val = 3, left = 0x0, right = 0x15d1100, next = 0x0}
(gdb) p *p
$8 = {val = 3, left = 0x0, right = 0x15d1100, next = 0x0}
(gdb) p *nextStart
$9 = {val = 2, left = 0x15d10a0, right = 0x15d10d0, next = 0x15d1070}
(gdb) c
Continuing.
Breakpoint 1, Solution::handle (this=0x7fff7657bd37, last=@0x7fff7657bd08: 0x0, p=@0x15d1048: 0x15d10a0,
nextStart=@0x7fff7657bd00: 0x0) at leetcode117.cpp:23
23 if (last) {
(gdb) p *last
Cannot access memory at address 0x0
(gdb) p *p
$10 = {val = 4, left = 0x0, right = 0x0, next = 0x0}
(gdb) p *nextStart
Cannot access memory at address 0x0
(gdb) c
Continuing.
Breakpoint 2, Solution::handle (this=0x7fff7657bd37, last=@0x7fff7657bd08: 0x15d10a0, p=@0x15d1048: 0x15d10a0,
nextStart=@0x7fff7657bd00: 0x15d10a0) at leetcode117.cpp:31
31 }
(gdb) p *last
$11 = {val = 4, left = 0x0, right = 0x0, next = 0x0}
(gdb) p *p
$12 = {val = 4, left = 0x0, right = 0x0, next = 0x0}
(gdb) p *nextStart
$13 = {val = 4, left = 0x0, right = 0x0, next = 0x0}
(gdb) c
Continuing.
Breakpoint 1, Solution::handle (this=0x7fff7657bd37, last=@0x7fff7657bd08: 0x15d10a0, p=@0x15d1050: 0x15d10d0,
nextStart=@0x7fff7657bd00: 0x15d10a0) at leetcode117.cpp:23
23 if (last) {
(gdb) p *last
$14 = {val = 4, left = 0x0, right = 0x0, next = 0x0}
(gdb) p *p
$15 = {val = 5, left = 0x0, right = 0x0, next = 0x0}
(gdb) p *nextStart
$16 = {val = 4, left = 0x0, right = 0x0, next = 0x0}
(gdb) c
Continuing.
Breakpoint 2, Solution::handle (this=0x7fff7657bd37, last=@0x7fff7657bd08: 0x15d10d0, p=@0x15d1050: 0x15d10d0,
nextStart=@0x7fff7657bd00: 0x15d10a0) at leetcode117.cpp:31
31 }
(gdb) p *last
$17 = {val = 5, left = 0x0, right = 0x0, next = 0x0}
(gdb) p *p
$18 = {val = 5, left = 0x0, right = 0x0, next = 0x0}
(gdb) p *nextStart
$19 = {val = 4, left = 0x0, right = 0x0, next = 0x15d10d0}
(gdb) c
Continuing.
Breakpoint 1, Solution::handle (this=0x7fff7657bd37, last=@0x7fff7657bd08: 0x15d10d0, p=@0x15d1080: 0x15d1100,
nextStart=@0x7fff7657bd00: 0x15d10a0) at leetcode117.cpp:23
23 if (last) {
(gdb) p *last
$20 = {val = 5, left = 0x0, right = 0x0, next = 0x0}
(gdb) p *p
$21 = {val = 6, left = 0x0, right = 0x0, next = 0x0}
(gdb) p *nextStart
$22 = {val = 4, left = 0x0, right = 0x0, next = 0x15d10d0}
(gdb) c
Continuing.
Breakpoint 2, Solution::handle (this=0x7fff7657bd37, last=@0x7fff7657bd08: 0x15d1100, p=@0x15d1080: 0x15d1100,
nextStart=@0x7fff7657bd00: 0x15d10a0) at leetcode117.cpp:31
31 }
(gdb) p *last
$23 = {val = 6, left = 0x0, right = 0x0, next = 0x0}
(gdb) p *p
$24 = {val = 6, left = 0x0, right = 0x0, next = 0x0}
(gdb) p *nextStart
$25 = {val = 4, left = 0x0, right = 0x0, next = 0x15d10d0}
(gdb) c
![【python基础】python切片—如何理解[-1:]，[:-1]，[::-1]的用法](https://img-blog.csdnimg.cn/ebbdf6cc99254ecdbc5d7843e4fbf1a0.png#pic_center)
