給你二叉搜尋樹的根節點 root ,該樹中的兩個節點被錯誤地交換。請在不改變其結構的情況下,恢複這棵樹。
進階:使用 O(n) 空間複雜度的解法很容易實作。你能想出一個隻使用常數空間的解決方案嗎?
示例 1:
輸入: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);
}
}