[LeetCode]Recover Binary Search Tree

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

示例 1:

输入: [1,3,null,null,2]
示例 2:

输入: [3,1,4,null,null,2]

使用 O(n) 空间复杂度的解法很容易实现,代码如下

class Solution {
    public void recoverTree(TreeNode root) {
        List<TreeNode> node = new ArrayList<TreeNode>();
        List<Integer> value = new ArrayList<Integer>();
        inorder(root,node,value);
        Collections.sort(value);
        for (int i = 0; i < node.size(); i++) {
            node.get(i).val = value.get(i);
        }
    }
    private void inorder(TreeNode root, List<TreeNode> node, List<Integer> value) {
        if (root == null)
            return;
        inorder(root.left,node,value);
        node.add(root);
        value.add(root.val);
        inorder(root.right,node,value);
    }
}