数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中每个节点填充下一个右侧指针
假设我们有一个完整的二叉树，其中每个节点具有以下字段：(数据、左、右、下一个)，左将指向左子树，右将指向右子树，下一个指针将指向下一个节点。如果右侧没有节点，则该节点将为 null。因此，最初每个下一个指针都设置为 null，我们必须建立链接。假设树像第一个一样，它将转换为下一个节点 -
为了解决这个问题，我们将遵循以下步骤 -
- 设置 pre := root，nextPre := null 和 prev := null
- 当 pre 不为 null 时
- 当 pre 不为 null 时
- 如果 pre 的左子节点不为 null
- 设置 prev 的 next := pre 的左子节点，当 prev 不为 null 时，否则 nextPre := pre 的左子节点
- prev := pre 的左子节点
- 如果 pre 的右子节点不为 null
- 设置 prev 的 next := pre 的右子节点，当 prev 不为 null 时，否则 nextPre := pre 的右子节点
- prev := pre 的右子节点
- 如果 pre 的左子节点不为 null
- pre := nextPre
- 将 nextPre 设置为 null 并将 prev 设置为 null
- 当 pre 不为 null 时
- 返回 null
让我们看看以下实现以获得更好的理解 -
示例
#include <bits/stdc++.h>
#include <stack>
using namespace std;
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() {}
Node(int _val, Node* _left, Node* _right) {
val = _val;
left = _left;
right = _right;
next = NULL;
}
};
class Solution {
public:
Node* connect(Node* root) {
Node* pre = root;
Node* nextPre = NULL;
Node* prev = NULL;
while(pre){
while(pre){
//cout << pre->val << endl;
if(pre->left){
if(prev){
prev->next = pre->left;
}else{
nextPre = pre->left;
}
prev = pre->left;
}
if(pre->right){
if(prev){
prev->next = pre->right;
}else{
nextPre = pre->right;
}
prev = pre->right;
}
pre = pre->next;
}
//cout << "*" << endl;
pre = nextPre;
nextPre = NULL;
prev = NULL;
}
return root;
}
};
void printTree(Node* root) {
cout << "[";
if (root == NULL) return;
queue<Node*> q;
Node *curr;
q.push(root);
q.push(NULL);
while (q.size() > 1) {
curr = q.front();
q.pop();
if (curr == NULL){
q.push(NULL);
}
else {
// if(curr->next)
// q.push(curr->next);
if(curr->left)
q.push(curr->left);
if(curr->right)
q.push(curr->right);
if(curr->val == 0){
cout << "null" << ", ";
}else{
cout << curr->val << ", ";
if (curr->next == NULL) cout<<"#, ";
}
}
}
cout << "]"<<endl;
}
int main() {
Node* root;
Node nodeFour(4, NULL, NULL);
Node nodeFive(5, NULL, NULL );
Node nodeSeven(7, NULL, NULL);
Node nodeSix(6, NULL, NULL);
Node nodeTwo(2,&nodeFour,&nodeFive);
Node nodeThree(3,&nodeSix,&nodeSeven);
Node nodeOne(1,&nodeTwo,&nodeThree);
root = &nodeOne;
Solution ob;
root = ob.connect(root);
printTree(root);
}输入
[1,2,3,4,5,6,7] Node* root; Node nodeFour(4, NULL, NULL); Node nodeFive(5, NULL, NULL ); Node nodeSeven(7, NULL, NULL); Node nodeSix(6, NULL, NULL); Node nodeTwo(2,&nodeFour,&nodeFive); Node nodeThree(3,&nodeSix,&nodeSeven); Node nodeOne(1,&nodeTwo,&nodeThree); root = &nodeOne; Solution ob; root = ob.connect(root);
输出
[1, #, 2, 3, #, 4, 5, 6, 7, #, ]
更新于: 2020-04-29
203 次浏览
广告