資料結構
網路連線
RDBMS
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法律學C++ 中恢復二叉搜尋樹
假設我們有一個二叉搜尋樹，現在考慮一下這個 BST 的兩個元素被交換了，所以我們必須恢復這棵二叉搜尋樹。
因此，如果給定的樹像下面這樣（第一個），那麼恢復的樹將是（第二個） −
要解決這個難題，我們將遵循以下步驟 −
定義一些用於節點的 prev、first 和 second 引用
定義一個名為 findProblem() 的方法，這將使用該節點
如果該節點為 null，則返回
呼叫 findProblem(該節點的左節點)
如果 prev 不為 null 且 prev 的值 > 該節點的值，則
如果 first 為 null，則 first = prev
second := node
prev := node
呼叫 findProblem(該節點的右節點)
在主方法中，執行以下操作 −
將 prev、first 和 second 初始化為 null，呼叫 findProblem(根節點) 然後交換 first 和 second 節點的值
示例（C++）
讓我們看看以下實現以更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
} else {
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
} else {
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
void tree_level_trav(TreeNode*root){
if (root == NULL) return;
cout << "[";
queue q;
TreeNode *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->left)
q.push(curr->left);
if(curr->right)
q.push(curr->right);
if(curr == NULL || curr->val == 0){
cout << "null" << ", ";
}else{
cout << curr->val << ", ";
}
}
}
cout << "]"<<endl;
}
class Solution {
public:
TreeNode* prev;
TreeNode* first;
TreeNode* second;
void swapValue(TreeNode* first, TreeNode* second){
int x = first->val;
first->val = second -> val;
second->val = x;
}
void findProblem(TreeNode* node){
if(!node || node->val == 0)return;
findProblem(node->left);
if((prev!=NULL && prev->val != 0) && prev->val> node->val){
if(!first){
first = prev;
}
second = node;
}
prev = node;
findProblem(node->right);
}
void recoverTree(TreeNode* root) {
prev = first = second = NULL;
findProblem(root);
swapValue(first, second);
}
};
main(){
vector<int> v = {1,3,NULL,NULL,2};
TreeNode *root = make_tree(v);
Solution ob;
ob.recoverTree(root);
tree_level_trav(root);
}輸入
{1,3,NULL,NULL,2}輸出
[3, 1, null, null, 2, ]
更新於：2020 年 5 月 26 日
263 次瀏覽
廣告