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