二叉树的两个错误节点

CD169 找到搜索二叉树中两个错误的节点

如果两个节点交换,那么在中序遍历里就有至少一次降序,可能有两个相邻的节点交换,或者两个不相邻的节点交换,产生一个或两次降序。

代码


#include <bits/stdc++.h>
using namespace std;

// initialize binary tree
struct node {
    int val;
    node* left;
    node* right;
};

int n, rootIdx;
node* tree;

node* buildWithValue() {
    cin >> n >> rootIdx;
   node* tree = new node[n + 1];
    for(int i = 0; i < n; ++i) {
        int v, r, l, x;
        cin >> v >> l >> r >> x;
        tree[v] = node{x, &(tree[l]), &(tree[r])};
        if(l == 0) tree[v].left = nullptr;
        if(r == 0) tree[v].right = nullptr;
        
    }
    return &tree[rootIdx];
}

node* build() {
    cin >> n >> rootIdx;
   node* tree = new node[n + 1];
    for(int i = 0; i < n; ++i) {
        int v, r, l;
        cin >> v >> l >> r;
        tree[v] = node{v, &(tree[l]), &(tree[r])};
        if(l == 0) tree[v].left = nullptr;
        if(r == 0) tree[v].right = nullptr;
    }
    return &tree[rootIdx];
}



void clear() {
    delete tree;
}

//my code in here
vector<node*> vec;
void middle(node *root) {
    if(root == nullptr) return;
    middle(root->left);
    vec.push_back(root);
    middle(root->right);
}

void  Worry(node *root) {
   node *w1 = nullptr;
   node *w2 = nullptr; 
   w1 = w2 = 0;
   middle(root);
   for(int i = 0 ;i < vec.size() - 1; ++i) {
       if(vec[i] > vec[i + 1]) {
           w1 = w1 == nullptr ? vec[i] : w1;
           w2 = vec[i + 1];
       }
   }
    if(w1->val > w2->val ) swap(w1, w2);
    cout << w1->val << ' ' << w2->val << endl;
}




int main() {
    node* root = build();
    
    Worry(root);
    // write my code in here
    
    clear();
}

Comments