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

import java.util.*;

public class Main {

    static class Node{
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    /*如果对二叉搜索树进行中序排列（左根右），那么会得到一个从小到大的序列。
      如果中序遍历时出现两次降序，第一个错误的节点为第一次降序时较大的节点，第二个错误的节点为第二次降序时较小的节点

      如果中序遍历时出现一次降息，第一个错误的节点就是本次降序较大的节点，第二个错误的节点就是本次降序较小的节点
    * */
    public static Node[] getTwoErrNodes(Node head){
        Node[] errs=new Node[2];
        if(head==null){
            return errs;
        }

        Stack<Node> stack=new Stack<Node>();
        Node pre=null;
        //放入    根 左
        //弹出    左 根
        //放入    右
        //弹出    右
        while (!stack.isEmpty()|| head!=null){
            if(head!=null){
                stack.push(head);
                head=head.left;
            }else {
                head=stack.pop();
                if(pre!=null &&pre.value>head.value){
                    errs[0]= errs[0]==null?pre:errs[0];
                    errs[1]=head;
                }
                pre=head;
                head=head.right;
            }
        }

        return errs;
    }

    public static Node createTree(Scanner in, int n){
        int rootValue=in.nextInt();
        Node root=new Node(rootValue);
        HashSet<Node> set=new HashSet<Node>();
        set.add(root);

        //n行读取
        for (int i = 0; i < n; i++) {
            int fatherValue= in.nextInt();
            int leftValue=in.nextInt();
            int rightValue=in.nextInt();
            //遍历
            for (Node e:set){
                //1、比较节点
                if(e.value==fatherValue){
                    //2、建立左右节点
                    Node left= leftValue==0?null:new Node(leftValue);
                    Node right= rightValue==0?null:new Node(rightValue);
                    e.left=left;
                    e.right=right;
                    //3、放入节点
                    if(leftValue!=0){
                        set.add(left);
                    }
                    if(rightValue!=0){
                        set.add(right);
                    }
                    //4、remove
                    set.remove(e);
                    break;
                }
            }

        }


        return root;
    }

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        Node root=createTree(in,n);

        Node[] result=new Node[2];
        result=getTwoErrNodes(root);
        System.out.println(result[1].value+" "+result[0].value);
    }
}