C++刷leetcode（99. 恢复二叉搜索树）【递归】

糖逗

题目描述：

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

示例 1:

输入: [1,3,null,null,2]

   1
  /
 3
  \
   2

输出: [3,1,null,null,2]

   3
  /
 1
  \
   2
示例 2:

输入: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

输出: [2,1,4,null,null,3]

  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[i].val = input[i];
                res[i].left = NULL;
                res[i].right = NULL;
        }
        for(int i= 0; i < input.size(); i++){
                if(2*i+1 < input.size()){
                        res[i].left = &res[2*i+1];
                }
                if(2*i+2 < input.size()){
                        res[i].right = &res[2*i+2];
                }
                
        }
        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[depth][insert] = 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[i].size();j++){
                        if(res[i][j] == 0){
                                cout  << " ";
                        }
                        else{
                                cout << res[i][j];
                        }
                       
                }
                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[i]        << " ";
        }
        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[i]        << " ";
        }
        cout << endl;
        rever(root, temp);
       
        return;
   
}