AlgoPressAppearance
0099 恢复二叉搜索树
题目描述
https://leetcode.cn/problems/recover-binary-search-tree 给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。 示例 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 使二叉搜索树有效。
提示：
- 树上节点的数目在范围 [2, 1000] 内
- -2^31 <= Node.val <= 2^31 - 1 进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？
思路:dfs【me】
dfs，从根节点开始，分别从左边节点找出大于自己的节点，从右边节点找出小于自己的节点。 这样这两个节点是违反的，直接交换其数值。 这个算法有个问题，当测试用例是 [3,null,2,null,1] 的时候，就会出现计算错误，知识交换了 3,2 两个节点。
csharp
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
private TreeNode findLarge(TreeNode root, int v){
if(root == null){
return null;
}
if(root.val > v){
return root;
}
TreeNode left = findLarge(root.left,v);
if(left == null){
return findLarge(root.right,v);
}
return left;
}
private TreeNode findLess(TreeNode root, int v){
if(root == null){
return null;
}
if(root.val < v){
return root;
}
TreeNode left = findLess(root.left,v);
if(left == null){
return findLess(root.right,v);
}
return left;
}
public void RecoverTree(TreeNode root) {
if(root == null){
return;
}
TreeNode leftLarge = findLarge(root.left, root.val);
TreeNode rightLess = findLess(root.right, root.val);
if(leftLarge != null && rightLess != null){
int temp = leftLarge.val;
leftLarge.val = rightLess.val;
rightLess.val = temp;
}
else if(leftLarge != null){
int temp = leftLarge.val;
leftLarge.val = root.val;
root.val = temp;
}
else if(rightLess != null){
int temp = root.val;
root.val = rightLess.val;
rightLess.val = temp;
}
else{
RecoverTree(root.left);
RecoverTree(root.right);
}
}
}
思路2：中序遍历
中序遍历应该是顺序递增的，将中序遍历结果放到 List 中，然后从两端查找不符合递增的节点，交换他们的数值。
csharp
public class Solution {
private List<TreeNode> list;
private void dfs(TreeNode root){
if(root == null){
return;
}
dfs(root.left);
list.Add(root);
dfs(root.right);
}
public void RecoverTree(TreeNode root) {
list = new List<TreeNode>();
dfs(root);
TreeNode left=null;
TreeNode right=null;
for(int i=0; i<list.Count-1; i++){
if(list[i].val > list[i+1].val){
left = list[i];
break;
}
}
for(int i=list.Count-1; i>=1; i--){
if(list[i].val < list[i-1].val){
right = list[i];
break;
}
}
if(left != null && right != null){
int temp = left.val;
left.val = right.val;
right.val = temp;
}
}
}
思路3： 中序遍历，缓存 pre
csharp
public class Solution {
TreeNode pre,left,right;
private void dfs1(TreeNode root){
if(root == null){return;}
dfs1(root.left);
if(pre != null && pre.val > root.val){
left = pre;
return;
}
pre = root;
dfs1(root.right);
}
private void dfs2(TreeNode root){
if(root == null){return;}
dfs2(root.right);
if(pre != null && pre.val < root.val){
right = pre;
return;
}
pre = root;
dfs2(root.left);
}
public void RecoverTree(TreeNode root) {
dfs1(root);
pre = null;
dfs2(root);
if(left != null && right != null){
int temp = left.val;
left.val = right.val;
right.val = temp;
}
}
}