leetcode-99 Recover Binary Search Tree

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

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]   1   /  3   \   2 Output: [3,1,null,null,2]   3   /  1   \   2

Example 2:

Input: [3,1,4,null,null,2] 3 / \ 1 4   /   2 Output: [2,1,4,null,null,3] 2 / \ 1 4   /  3

题意：将树的节点进行更正数字，使其成为正确的二叉搜索树。

二叉搜索树的中序是一个递增列表，根据这个我们可以对每个节点数据，生成一个list后，对其排序

，然后重新设值：

    public void recoverTree(TreeNode root) {                  List<Integer> value = new ArrayList<>();         getValue(value,root);         Collections.sort(value);         setValue(value,root);     }          public void getValue(List<Integer> value,TreeNode root) {         if(root == null) {             return;         }         if(root.left!=null) {             getValue(value,root.left);         }         value.add(root.val);         if(root.right!=null) {             getValue(value,root.right);         }     }          public void setValue(List<Integer> value,TreeNode root) {         if(root == null) {             return;         }         if(root.left!=null) {             setValue(value,root.left);         }         root.val = value.get(0);         value.remove(0);         if(root.right!=null) {             setValue(value,root.right);         }     }