C++刷leetcode（99. 恢复二叉搜索树）【递归】
本帖最后由 糖逗 于 2020-5-8 17:46 编辑题目描述：
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 1:
输入:
1
/
3
\
2
输出:
3
/
1
\
2
示例 2:
输入:
3
/ \
1 4
/
2
输出:
2
/ \
1 4
/
3
进阶:
使用 O(n) 空间复杂度的解法很容易实现。
你能想出一个只使用常数空间的解决方案吗？
#include<iostream>
#include <malloc.h>
#include <vector>
#include <math.h>
#include <queue>
#include<algorithm>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(NULL), right(NULL){
}
};
TreeNode* CreateTree(vector<int> input){
TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
for(int i = 0; i < input.size(); i++){
res.val = input;
res.left = NULL;
res.right = NULL;
}
for(int i= 0; i < input.size(); i++){
if(2*i+1 < input.size()){
res.left = &res;
}
if(2*i+2 < input.size()){
res.right = &res;
}
}
return res;
}
void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
if(root == NULL) return;
int insert = left + (right - left) / 2;
res = root->val;
middle(root->left, res, left, insert - 1, depth + 1);
middle(root->right, res, insert + 1, right, depth + 1);
}
int treeDepth(TreeNode* root){
if(root == NULL || root -> val == 0) return 0;
return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
}
void PrintTree(TreeNode* root) {
int depth = treeDepth(root);
int width = pow(2, depth) - 1;
vector<vector<int> > res(depth, vector<int>(width, 0));
middle(root, res, 0, width - 1, 0);
for(int i = 0; i < res.size(); i++){
for(int j = 0; j < res.size();j++){
if(res == 0){
cout<< " ";
}
else{
cout << res;
}
}
cout << endl;
}
cout << "------------------" << endl;
}
void inorder(TreeNode* root, vector<int>& temp){
if(root == NULL) return;
inorder(root -> left, temp);
if(root -> val != 0)temp.push_back(root -> val);
inorder(root -> right, temp);
}
void rever(TreeNode* root, vector<int>& temp){
if(root == NULL) return;
rever(root -> left, temp);
if(root -> val != 0){
if(root -> val != temp.front()){
root -> val = temp.front();
temp.erase(temp.begin());
}
else{
temp.erase(temp.begin());
}
}
rever(root -> right, temp);
}
void solution(TreeNode* root) {
if(root == NULL) return;
vector<int> temp;
inorder(root, temp);
sort(temp.begin(), temp.end());
for(int i =0; i < temp.size(); i++){
cout << temp << " ";
}
cout << endl;
rever(root, temp);
return;
}
int main(void){
vector<int> input;
int number;
while(cin >> number){
input.push_back(number);
}
TreeNode* root = CreateTree(input);
PrintTree(root);
solution(root);
PrintTree(root);
return 0;
}
注意事项：
1.中序遍历的二叉查找树的升序排列。
2.自己定义的树是用0代表缺失值的所以和leetcode上有些许不同（做了节点值是否为0的判断）。 新增代码
void inorder(TreeNode* root, vector<int>& temp){
if(root == NULL) return;
inorder(root -> left, temp);
if(root -> val != 0)temp.push_back(root -> val);
inorder(root -> right, temp);
}
void rever(TreeNode* root, vector<int>& temp){
if(root == NULL) return;
rever(root -> left, temp);
if(root -> val != 0){
if(root -> val != temp.front()){
root -> val = temp.front();
temp.erase(temp.begin());
}
else{
temp.erase(temp.begin());
}
}
rever(root -> right, temp);
}
void solution(TreeNode* root) {
if(root == NULL) return;
vector<int> temp;
inorder(root, temp);
sort(temp.begin(), temp.end());
for(int i =0; i < temp.size(); i++){
cout << temp << " ";
}
cout << endl;
rever(root, temp);
return;
}
页:
[1]