博客

题目概述

解题思路

这道题的目标是，让我们找一棵搜索二叉树中，元素放错位置的两个节点的值。因为树中各个节点的值不相等，所以根据搜索二叉树的性质可知，这棵树（元素正确放置）的所有节点的中序遍历结果，一定是一个升序的数组。当数组的元素错放时，我们只需要找出这两个错放的元素位置即可。

我们只需要从前往后遍历，找到第一个次出现这种情况的元素A[i]：

从后往前遍历，找到第一个出现这种情况的元素A[j]：

这样就找到了所需的两个值。

方法性能

上述方法的时间复杂度是O(N)。

示例代码

#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<vector>

using namespace std;

class TreeNode
{   
    public:
        int val;
        TreeNode *L, *R;
};

void midOrder(TreeNode* root, vector<int> & res)
{
    if(root == NULL)
        return;

    midOrder(root->L, res);
    res.push_back(root->val);
    midOrder(root->R, res);
}

int main()
{
    int N, R, ri, Li, Ri;
    scanf("%d%d", &N, &R);
    vector<TreeNode> trees;
    trees.resize(N + 1);

    for (int i = 0; i < N; ++i)
    {
        scanf("%d%d%d", &ri, &Li, &Ri);
        trees[ri].val = ri;
        if(Li == 0)
            trees[ri].L = NULL;
        else
            trees[ri].L = &trees[Li];
        if(Ri == 0)
            trees[ri].R = NULL;
        else
            trees[ri].R = &trees[Ri];
    }

    vector<int> ori;
    midOrder(&trees[R], ori);

    int sma, lar;

    for (int i = 0; i < ori.size() - 1; ++i)
    {
        if(ori[i] > ori[i + 1])
        {
            sma = ori[i];
            break;
        }
    }

    for (int j = ori.size() - 1; j > 0; --j)
    {
        if(ori[j] < ori[j - 1])
        {
            lar = ori[j];
            break;
        }
    }

    cout << lar << ' ' << sma << endl;
    return 0;
}