C++,迭代式中序遍历找出两个错误节点

利用迭代式中序遍历，找到两个错误的节点。 以中序遍历序列【1，2，6，4，5，3】为例，其两个错误的节点是6和3， 那么只有当遍历到4时，才能发现6是错误的节点，因此用x存储4的上一个节点，也就是6； 当遍历到第二个错误节点的时候，可以直接发现3小于5，用y存储当前节点就好。

    vector<int> findError(TreeNode* root) {
        // write code here
        stack<TreeNode*> stk;
        TreeNode* x = nullptr;
        TreeNode* y = nullptr;
        TreeNode* pred = nullptr;

        while (!stk.empty() || root != nullptr) {
            while (root != nullptr) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            if (pred != nullptr && root->val < pred->val) {
                y = root;
                if (x == nullptr) {
                    x = pred;
                }
                else break;
            }
            pred = root;
            root = root->right;
        }
        return {y->val, x->val};
    }

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/recover-binary-search-tree/solution/hui-fu-er-cha-sou-suo-shu-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。