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

代码如下

import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

public class Main {
    private static Map<Integer, TreeNode> cache = new HashMap<>();

    public static void main(String[]args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            int num = scanner.nextInt();
            int rootNum = scanner.nextInt();
            int n = num;
            int i = 0;
            int[][] info = new int[num][3];
            while(n > 0) {
                info[i][0] = scanner.nextInt();
                info[i][1] = scanner.nextInt();
                info[i][2] = scanner.nextInt();
                i++;
                n--;
            }
            TreeNode root = constructTree(info, rootNum);
            if (root == null) {
                continue;
            }
            Integer[] result = getErr(root);
            if (result[0] > result[1]) {
                int temp = result[0];
                result[0] = result[1];
                result[1] = temp;
            }
            System.out.printf("%d %d\n", result[0], result[1]);
        }
    }

    private static Integer[] getErr(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        Integer[] result = new Integer[2];
        TreeNode pre = null;
        while(!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                if (pre != null && pre.val > root.val) {
                    result[0] = result[0] == null ? pre.val : result[0];
                    result[1] = root.val;
                }
                pre = root;
                root = root.right;
            }
        }

        return result;
    }

    private static TreeNode constructTree(int[][] info, int rootNum) {
        for(int i = 0;i < info.length;i++) {
            TreeNode curNode = getAndCache(info[i][0]);
            TreeNode leftNode = getAndCache(info[i][1]);
            TreeNode rightNode = getAndCache(info[i][2]);
            curNode.left = leftNode;
            curNode.right = rightNode;

        }
        return cache.get(rootNum);
    }

    private static TreeNode getAndCache(int val) {
        if (val == 0) {
            return null;
        }
        TreeNode cur = cache.get(val);
        if (cur == null) {
            cur = new TreeNode(val);
            cache.put(val, cur);
        }
        return cur;
    }
}

搜索二叉树中序遍历的结果是数字从小到大排列，题目中给出条件每个数都不同，且仅有两个数位置错误，那么第一次遇到顺序错误的第一个元素和第二次遇到顺序错误的第二个元素即为所需答案。
第一次顺序错误一定是高->低，所以前面那个高的错了，第二次顺序错误也是高->低，此时是低的那个错了。
打印的答案按照从小到大排列，否则会错误。