题解 | 找到搜索二叉树中两个错误的节点

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <climits>
class Solution {
public: 
    //这个数比后面的数大，则这是交换的数中大的那个数；
    //这个数比前面的数小则，这是交换的数中小的那个数;
    vector<int> findError(TreeNode* root) {
        if(!root){
            return {};
        }

        vector<int> ans(2);

        find_two(ans, root);

        return ans;
    }

    void find_two(vector<int>& ans, TreeNode* root){
        int index = 1;
        TreeNode* pre_node = nullptr;
        TreeNode* curr = root;  //作为我们要处理的节点

        stack<TreeNode*> stk;
        //层序遍历使用队列，先入队初始化，再遍历；
        //中序遍历使用栈，栈初始为空；
        while(curr || !stk.empty()){  //要么使用curr有节点的情况，或者是栈有节点的情况；
            while( curr ){     //不应该检测栈顶节点是否有左节点，不然左节点会重复入栈
                stk.push(curr);
                curr = curr->left;
            }

            curr = stk.top();stk.pop();
          //交换的较大值在前面，比左右两边大，交换的较小值在后面，比左右两边小；
		  //第一次遇到后值小的，则较大的交换值就确定了，后续遇到后值小的情况时，只需更新较小值，
            if(pre_node && curr->val < pre_node->val){
                if(index == 1){
                    ans[index] = pre_node->val;
                    ans[0] = curr->val;
                    index = 0;
                }else{
                    ans[0] = curr->val;
                }
            }
            pre_node = curr;

            curr = curr->right;  
        }
    }
};