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

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    TreeNode preNode = null;
    TreeNode firstNode = null;
    TreeNode secondNode = null;

    public void inorder(TreeNode node) {
        if (node == null) {
            return;
        }

        inorder(node.left);
        if (preNode != null && preNode.val > node.val) {
            if (firstNode == null) {
                firstNode = preNode;
            }
            secondNode = node;
        }
        preNode = node;

        inorder(node.right);
    }
    public int[] findError (TreeNode root) {
        inorder(root);
        return firstNode.val < secondNode.val ?
               new int[] {firstNode.val, secondNode.val} :
               new int[] {secondNode.val, firstNode.val};
    }
}

int minVal=Integer.MIN_VALUE ,p1=0 ,p2=0;

public int[] findError (TreeNode root) {
    // write code here
    dfs(root);
    return new int[]{p2 ,p1};
}

public void dfs(TreeNode root){
    if(root==null){
        return;
    }
    dfs(root.left);
    if(minVal>root.val){
        if(p1==0){
            p1=minVal;
            p2=root.val;
        }else{ // 如果第二次出现了逆序，则第二次逆序的小值为错误节点
            p2=root.val;
        }
    }
    minVal=root.val;
    dfs(root.right);
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 the root
     * @return int整型一维数组
     */
    public int[] findError (TreeNode root) {
        // write code here
        if(root==null){
            return null;
        }
        ArrayList<Integer> list=new ArrayList<>();
        mid(root,list);
        int arr[]=new int[2];
        for(int i=0;i<list.size()-1;i++){
            for(int j=i+1;j<list.size();j++){
                //交换后判断是否递增
                int tmp=list.get(i);
                list.set(i,list.get(j));
                list.set(j,tmp);
                if(isUP(list)==true){
                    arr[0]=list.get(i);
                    arr[1]=list.get(j);
                    return arr;
                //不符合递增就变回去进行下一轮判断
                }else{
                    tmp=list.get(i);
                    list.set(i,list.get(j));
                    list.set(j,tmp);
                }
            }
        }

        return null;
    }
    public void mid(TreeNode root,ArrayList<Integer> list){
        if(root==null){
            return;
        }
        mid(root.left,list);
        list.add(root.val);
        mid(root.right,list);
    }
    public boolean isUP(ArrayList<Integer> list){
        for(int i=1;i<list.size();i++){
            if(list.get(i)<list.get(i-1)){
                return false;
            }
        }
        return true;
    }
}

import java.util.*;

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

public class Solution {
    /**
     * 
     * @param root TreeNode类 the root
     * @return int整型一维数组
     */
    TreeNode first=null;
    TreeNode second=null;
    TreeNode pre=new TreeNode(Integer.MIN_VALUE);
    public int[] findError (TreeNode root) {
        // write code here
        //中序遍历找到这两个节点
        inorder(root);
//         TreeNode tem=first;
//         first.val=second.val;
//         second.val=tem.val;
        return new int[]{second.val,first.val};
    }
    public void inorder(TreeNode root){
        if(root==null){
            return;
        }
        inorder(root.left);
        if(root.val<pre.val){
            //出现错误的情况
            if(first==null){
                first=pre;
            }
            second=root;
        }
        pre=root;
        inorder(root.right);
    }
}

import java.util.*;
/**
七刷
解题思路：
1. 先用中序遍历遍历树，得到一个部分排序数组，该数组中有两个数交换了位置，
   现在的问题变成了从一个部分有序的数组中找出交换了位置的那两个数

2. 因为此时的情况必定是一个小的数放到了后面，一个大的数放到了前面
   所以从左往右找那个大的数，并记录下索引，从右往左找小的那个数，并且索引值必大于前面记录下的索引
*/
public class Solution {
    List<Integer> list = new ArrayList();
    public int[] findError (TreeNode root) {
        int[] result = new int[2];
        if(root == null) {
            return result;
        }
        findErrorHelper(root);
        int i, j;
        for(i = 0; i < list.size() - 1; i++) {
            if(list.get(i) > list.get(i + 1)) {
                result[1] = list.get(i);
                break;
            }
        }
        for(j = list.size() - 1; j > i; j--) {
            if(list.get(j) < list.get(j - 1)) {
                result[0] = list.get(j);
                break;
            }
        }
        return result;
    }

    private void findErrorHelper(TreeNode root) {
        if(root != null) {
            findErrorHelper(root.left);
            list.add(root.val);
            findErrorHelper(root.right);
        }
    }
}

import java.util.*;

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

public class Solution {
    /**
     * 
     * @param root TreeNode类 the root
     * @return int整型一维数组
     */
    public ArrayList<Integer> arr = new ArrayList<>();
    public int[] findError (TreeNode root) {
        // write code here
        int[] ans = new int[2];
        inOrder(root);
        ArrayList<Integer> reversed = new ArrayList<>();
        for(int i = 0; i < arr.size()-1; i++) {
            if(arr.get(i) > arr.get(i+1)) {
                reversed.add(i);
            }
        }
        if(reversed.size() == 1) {
            int idx = reversed.get(0);
            ans = new int[]{arr.get(idx), arr.get(idx+1)};
        }
        if(reversed.size() == 2) {
            int idx1 = reversed.get(0), idx2 = reversed.get(1)+1;
            ans = new int[]{arr.get(idx1), arr.get(idx2)};
        }
        Arrays.sort(ans);
        return ans;
    }
    public void inOrder(TreeNode root) {
        if(root == null) return;
        inOrder(root.left);
        arr.add(root.val);
        inOrder(root.right);
    }
}

import java.util.*;

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

public class Solution {
    
    int[] result = new int[2]; // 找到的目标节点
    int findCount = 0; // 找到目标节点的数量，总数为2
    int pre = 0; // 前继节点值
    boolean hasPre = false; // 中序遍历是否有前继节点
    
    // 有时候函数太多的时候就将其作为全局变量，或者有些递归函数需要的是变量值的实时情况，这个时候也需要全局变量。
    // 想法：中序遍历整个树，然后找到两个降序对，第一个降序对的第一个节点值是较大数，第二个降序对的第二个节点值是较小数
    public int[] findError (TreeNode root) {
        // write code here
        if (root.left == null && root.right == null) {
            return new int[]{};
        }
        
        inorder(root);
        
        return result;
    }
    
    private void inorder(TreeNode node) {
        if (node != null && findCount != 2) {
            if (node.left != null) {
                inorder(node.left);
            }
            
            if (hasPre) {
                if (pre > node.val) {
                    if (findCount == 0) {
                        result[1] = pre;
                        findCount++;
                    } else {
                        result[0] = node.val;
                        findCount++;
                    }
                }
            }
            pre = node.val;
            hasPre = true;
            
            if (node.right != null) {
                inorder(node.right);
            }
        }
    }
} 

import java.util.*;


public class Solution {

    int idx = 1;
    int prev = Integer.MIN_VALUE;
    int tmp = 0;
    
    public int[] findError (TreeNode root) {
        int[] res = new int[2];
        inorder(root, res);
        if (idx == 0) {
            res[idx] = tmp;
        }
        return res;
    }
    
    public void inorder(TreeNode root, int[] res) {
        if (root == null) {
            return;
        }
        
        inorder(root.left, res);
        if (prev != Integer.MIN_VALUE) {
            if (root.val < prev) {
                if (idx == 1) {
                    res[idx--] = prev;
                    tmp = root.val;
                }else {
                    res[idx--] = root.val;
                    tmp = prev;
                }
            }
        }
        prev = root.val;
        inorder(root.right, res);
    }
}