https://leetcode.com/problems/recover-binary-search-tree/

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:

A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

解题思路：

这道题的难点首先就在于，如何判断一个node的位置是错误的？

思考BST的定义，左子树的所有节点都<=root的值，右子树的所有节点都>root的值，并且所有子树也是这样。这是一个递归的定义。所以，就不能DFS的时候，仅仅判断当前节点是不是不比左节点小，并且比右节点小。这样的判断是无效的。

回想  这道题，我们能发现BST的一个重要性质——BST的inorder遍历结果，是单调递增的。那么如果一个BST有两个节点交换了位置，出来的结果一定有错误。但是，会有几处错误呢？

第一种情况，0,1,2这样的BST，变成了1,0,2，一处错误。

第二种情况，0,1,2,3,4,5,6，变成0,5,2,3,4,1,6。两处错误。

于是，思路是：inorder遍历BST，遇到当前节点val比前一个节点小的，说明出错了。第一种情况，当前节点和前一个节点换一下就可以了。第二种情况，第一个错误地方的前一个节点，和第二个错误地方的当前节点交换就可以了。

那么我们可以遇到第一次错误的时候，将前一个节点和当前节点都加入列表。后面出现错误，只要用当前节点去替换第二个位置就可以了。

代码如下：

/** * Definition for binary tree * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public void recoverTree(TreeNode root) {        List
     
       list = new ArrayList
      
       ();        List
       
         preList = new ArrayList
        
         ();        dfs(root, list, preList);        TreeNode node1 = list.get(0);        TreeNode node2 = list.get(1);            int temp = node1.val;        node1.val = node2.val;        node2.val = temp;    }        public void dfs(TreeNode root, List
         
           list, List
          
            preList) { if(root == null) { return; } dfs(root.left, list, preList); if(preList.size() == 0) { preList.add(root); } else { if(root.val < preList.get(0).val) { if(list.size() == 0) { list.add(preList.get(0)); list.add(root); } else { list.set(1, root); //说明两个节点已经都找出来了，不要再递归下去了 return; } } preList.set(0, root); } dfs(root.right, list, preList); }}
          
         
        
       
      
     

这道题，preNode为什么一定要用一个list来存，而不能直接用TreeNode？如果写成下面的样子会如何？

/** * Definition for binary tree * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public void recoverTree(TreeNode root) {        List
     
       list = new ArrayList
      
       ();        TreeNode preNode = null;        dfs(root, list, preNode);        TreeNode node1 = list.get(0);        TreeNode node2 = list.get(1);            int temp = node1.val;        node1.val = node2.val;        node2.val = temp;    }        public void dfs(TreeNode root, List
       
         list, TreeNode preNode) {        if(root == null) {            return;        }        dfs(root.left, list, preNode);        if(preNode == null) {            preNode = root;        } else {            if(root.val < preNode.val) {                if(list.size() == 0) {                    list.add(preNode);                    list.add(root);                } else {                    list.set(1, root);                    //说明两个节点已经都找出来了，不要再递归下去了                    return;                }            }            preNode = root;        }        dfs(root.right, list, preNode);    }}
       
      
     

Runtime Error Message:	Line 15: java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
Last executed input:	{0,1}

这是因为Java传参都是pass by value，而递归调用每个方法都有自己的栈，所以这里preNode == null的时候，将preNode置为root，其实只是在当前方法栈中的操作。递归return后，上一层的preNode仍然是null。

而list就不同了，虽然list也是pass by value，但对它的内容进行更改，确是固定在堆上的。这里就要理解Java内存中，堆和栈的区别。所以list.add()或者list.set()的方法是相当于全局变量生效的。这也是为什么在前面很多dfs题目里，我们都会在递归方法的参数里，用一个list来保存结果的原因。

这道题我没做出来，看的大神的结果。

http://blog.csdn.net/linhuanmars/article/details/24566995

//20181121

/** * Definition for binary tree * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public void recoverTree(TreeNode root) {        List
     
       list = new ArrayList
      
       ();        TreeNode[] preNode = new TreeNode[1];        preNode[0] = new TreeNode(Integer.MIN_VALUE);        dfs(root, list, preNode);        TreeNode node1 = list.get(0);        TreeNode node2 = list.get(1);            int temp = node1.val;        node1.val = node2.val;        node2.val = temp;    }        public void dfs(TreeNode root, List
       
         list, TreeNode[] preNode) {        if(root == null) {            return;        }        dfs(root.left, list, preNode);        if(root.val < preNode[0].val) {           if(list.size() == 0) {               //第一次遇到错误节点                list.add(preNode[0]);                list.add(root); //这里不能少，因为有只错一次的第一种情况            } else {               //此时第一个错误节点的前一个节点已经置上去了，只需要置第二个值                list.set(1, root);                //说明两个节点已经都找出来了，不要再递归下去了                return;            }        }        preNode[0] = root;        dfs(root.right, list, preNode);    }}