資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告