[数据结构与算法]找到搜索二叉树中两个错误的节点

分析

二叉搜索树的中序遍历是一个升序序列，而交换其中两个节点后的遍历序列中可能会有两个逆序对，如（1,2，3,4，5）交换2和4（1,4，3,2，5），存在逆序对(4,3)和(3,2),第一个逆序对的第一个数个第二个逆序对的第二个数就是二叉树中交换的两个数；如果遍历序列中只有一个逆序对，那么逆序对中的两个数就是交换的两个数。

代码：

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 int[] findError (TreeNode root) {
        // write code here
        List<Integer> list = new ArrayList<>();
        Inorder(root,list);
        //查找两个降序对
        List<int[]> r = new ArrayList();
        for(int i = 0; i < list.size()-1;i++) {
          if(list.get(i) > list.get(i+1)) {
              r.add(new int[]{list.get(i),list.get(i+1)});
          }
        }
        if(r.size() == 1) {
            return new int[] {r.get(0)[1],r.get(0)[0]};
        } else {
            return new int[]{r.get(1)[1],r.get(0)[0]};
        }
        
    }              
    
   public void Inorder(TreeNode root,List<Integer> list) {
       if(root == null) {
           return;
       }
        Inorder(root.left,list);
       list.add(root.val);
       Inorder(root.right,list);
   }
}