程序员代码面试指南 3.10：找到搜索二叉树中两个错误的节点

1、思路

• 对二叉树进行中序遍历得到的节点值是升序的，若出现降序的情况，说明找到了错误的节点，降序分两种情况讨论： 1、中序遍历时节点值出现两次降序，如[1, 5, 3, 4, 2]，第一次降序为5->3，第二次降序为4->2； 2、中序遍历时节点值出现一次降序，如[1, 2, 4, 3, 5]，只有一次降序为4->3；

• 寻找两个错误节点的过程可以总结为：第一个错误节点为第一次降序时较大的节点，第二个错误节点为最优一次降序时较小的节点。

2、代码

#include 
#include 
#include 

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;

    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
};

void createTree(TreeNode *root, int& n)    //建树
{
    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;

    root->val = rootVal;

    if (leftVal != 0)
    {
        root->left = new TreeNode(leftVal);
        createTree(root->left, -- n);
    }

    if (rightVal != 0)
    {
        root->right = new TreeNode(rightVal);
        createTree(root->right, -- n);
    }
}

vector getTwoErrNodes(TreeNode *root)
{
    vector errs(2, nullptr);
    stack stk;
    TreeNode *pre;

    //二叉树的中序遍历，迭代法
    while (!stk.empty() || root != nullptr)
    {
        if (root != nullptr)
        {
            stk.push(root);
            root = root->left;
        }
        else
        {
            root = stk.top();
            stk.pop();

            //判断前一节点是否大于当前节点，即出现降序
            if (pre != nullptr && pre->val > root->val)
            {
                //判断是否为第一次降序
                errs[0] = errs[0] == nullptr ? pre : errs[0];
                errs[1] = root;
            }

            pre = root;
            root = root->right;
        }
    }

    return errs;
}

int main()
{
    int n, rootVal;
    cin >> n >> rootVal;

    TreeNode *root = new TreeNode(rootVal);
    createTree(root, n);

    auto res = getTwoErrNodes(root);
    cout val val << endl;

    return 0;    
}