数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法学研究C++ 实现每个节点的下一个右侧指针 II
假设我们有一棵二叉树，每个节点都有以下字段：(数据，左子树，右子树，下一个节点)，左子树指针指向左子树，右子树指针指向右子树，“下一个节点”指针指向下一个节点。如果右侧没有节点，则该指针为 null。因此，最初每个“下一个节点”指针都设置为 null，我们需要建立这些连接。假设树像第一个示例那样，它将转换为下一个节点：
为了解决这个问题，我们将遵循以下步骤：
- 设置 pre := 根节点, 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() : 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): 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);
Node nodeFive(5);
Node nodeSeven(7);
Node nodeTwo(2,&nodeFour,&nodeFive);
Node nodeThree(3,NULL,&nodeSeven);
Node nodeOne(1,&nodeTwo,&nodeThree);
root = &nodeOne;
Solution ob;
root = ob.connect(root);
printTree(root);
}输入
[1,2,3,4,5,null,7] Node* root; Node nodeFour(4); Node nodeFive(5); Node nodeSeven(7); Node nodeTwo(2,&nodeFour,&nodeFive); Node nodeThree(3,NULL,&nodeSeven); Node nodeOne(1,&nodeTwo,&nodeThree); root = &nodeOne;
输出
[1, #, 2, 3, #, 4, 5, 7, #, ]
更新于：2020年4月29日
106 次浏览
广告