给你二叉搜索树的根节点 root ,该树中的两个节点被错误地交换。请在不改变其结构的情况下,恢复这棵树。
进阶:使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗?
示例 1:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5CZmNGZyMmYhdDOmVmM1QDZkdDO3MTYjNDM1MGMkJ2Mz8CX0JXZ252bj91Ztl2Lc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
输入:root = [1,3,null,null,2]
输出:[3,1,null,null,2]
解释:3 不能是 1 左孩子,因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2:
输入:root = [3,1,4,null,null,2]
输出:[2,1,4,null,null,3]
解释:2 不能在 3 的右子树中,因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/recover-binary-search-tree
解题如下:
1.二叉搜索树的特点 左子树 < 根结点 < 右子树
2.中序遍历获得List<Integer>
3.找到两个需要交换的元素
4.恢复左子树,右子树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* 解题思路:
* 1.二叉搜索树,左子树 < 根结点 < 右子树
* 2.中序遍历获得ArrayList<Integerr> nums
* 3.找到需要替换的两个元素 int[x,y]
* 4.重建二叉搜索树
*/
public void recoverTree(TreeNode root) {
//1.中序遍历获得List<Integer>
List<Integer> nums = new ArrayList<>();
inorder(root, nums);
//2.找到两个需要交换的元素
int[] swappers = findTwoSwappers(nums);
//3.恢复左子树,右子树
recover(root, 2, swappers[0], swappers[1]);
}
void recover(TreeNode root, int count, int x, int y) {
if (root == null) return;
if (root.val == x || root.val == y) {
root.val = root.val == x ? y : x;
if (--count == 0) {
return;
}
}
recover(root.left, count, x, y);
recover(root.right, count, x, y);
}
int[] findTwoSwappers(List<Integer> nums) {
int x = -1, y = -1;
for (int i = 0;i < nums.size() - 1; i++) {
if (nums.get(i+1) < nums.get(i)) {
y = nums.get(i+1);
if (x == -1) {
x = nums.get(i);
} else {
break;
}
}
}
return new int[]{x,y};
}
void inorder(TreeNode root, List<Integer> nums) {
if(root == null) return;
inorder(root.left, nums);
nums.add(root.val);
inorder(root.right, nums);
}
}