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

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {

    public class ComparaInteger implements Comparator<Integer> {
        @Override
        public int compare(Integer num1, Integer num2) {
            return num1 - num2;
        }
    }
    /**
     *
     * @param root TreeNode类 the root
     * @return int整型一维数组
     */
    public int[] findError (TreeNode root) {
        // write code here
        ArrayList<Integer> arrayList = new
        ArrayList<>(); // 定义一个 ArrayList，用于存放最终的返回结果
        Stack<TreeNode> stack = new
        Stack<>(); // 定义一个辅助栈，用于实现中序遍历
        Queue<TreeNode> queue = new
        LinkedList<>(); // 定义一个队列，用于存放中序遍历的结果
        TreeNode tmpNode = root; // 定义一个辅助节点
        int tmpValue = 1; // 定义一个计数器

        // 中序遍历初始化
        while (null != tmpNode) {
            stack.push(tmpNode);
            tmpNode = tmpNode.left;
        }

        // 中序遍历的具体实现
        while (!stack.isEmpty()) {
            tmpNode = stack.pop(); // 从栈中弹出一个节点
            queue.add(tmpNode); // 将弹出的节点入队列
            if (null != tmpNode.right) { // 如果弹出的节点的右子树不为空
                tmpNode = tmpNode.right;
                while (null != tmpNode) {
                    stack.push(tmpNode);
                    tmpNode = tmpNode.left;
                }
            }
        }
        while (!queue.isEmpty()) {
            tmpNode = queue.poll();
            if (tmpValue != tmpNode.val) {
                arrayList.add(tmpNode.val);
            }
            tmpValue++;
        }
        arrayList.sort(new ComparaInteger()); // 返回最终结果前，进行排序
        return arrayList.stream().mapToInt(Integer::intValue).toArray();
    }
}