leetcode 99. Recover Binary Search Tree 复原二叉搜索树

题意

二叉搜索树有且只有一对节点被调换了，复原它

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

解1

最简单的方法：

中序遍历二叉树，把所有value存下来，然后排序，再依次赋值回去。

// Runtime: 4 ms, faster than 20.10% of Java online submissions for Recover Binary Search Tree. //Memory Usage: 39.2 MB, less than 14.45% of Java online submissions for Recover Binary Search Tree. public void recoverTree(TreeNode root) { List<Integer> list = new ArrayList<>(); List<TreeNode> nodes = new ArrayList<>(); helper(root, nodes, list); list.sort(Integer::compareTo); for (int i = 0; i < nodes.size(); i++) nodes.get(i).val = list.get(i); } private void helper(TreeNode root, List<TreeNode> nodes, List<Integer> list) { if (root == null) return; helper(root.left, nodes, list); nodes.add(root); list.add(root.val); helper(root.right, nodes, list); }

解2

/* ↑ | * | * | * | * | * | * | * | * | * | * | * ------------------------------------------------> 比较相邻的节点（inorder），如果当前val小于prev.val，则出现错乱，最多2处错乱（可能只有1处），swap即可。 有了思路随便怎么写都很好写了。 */ // Runtime: 2 ms, faster than 82.99% of Java online submissions for Recover Binary Search Tree. //Memory Usage: 39.2 MB, less than 14.45% of Java online submissions for Recover Binary Search Tree. TreeNode prev = null; TreeNode first = null; TreeNode second = null; public void recoverTree(TreeNode root) { inorder(root); swap(first, second); } private void swap(TreeNode first, TreeNode second) { int tmp = first.val; first.val = second.val; second.val = tmp; } private void inorder(TreeNode root) { if (root == null) return; inorder(root.left); if (prev != null && prev.val > root.val) { if (first == null) { first = prev; second = root; } else { second = root; return; } } prev = root; inorder(root.right); }