Leetcode 99. Recover Binary Search Tree

题目解析：

题目

解析：

这道题目的解法有很多，但是我在这边只介绍一种比较基本的也最容易理解的方法。解这道题的关键在于，二叉查找树的中序遍历是一个单调递增的序列。所以把错误的二叉查找树复原之后，第一个错误位置的元素会比他后一个元素大，而第二个错误的元素会比他前面的元素小，根据这样的规律就可以找出两个元素，所以具体的步骤如下：

将原树进行中序遍历找出被交换的两个元素遍历原树，修改相应两个位置的值

python代码如下：

def recoverTree(self, root: TreeNode) -> None: """ Do not return anything, modify root in-place instead. """ def inorder(root): return inorder(root.left)+[root.val]+inorder(root.right) if root else [] def find_swap(nums): x = y = -1 for i in range(len(nums)-1): if nums[i+1]<nums[i]: y = nums[i+1] if x==-1: x = nums[i] else: break return x,y def recover(root,count,x,y): if root: if root.val == x or root.val == y: root.val = y if root.val == x else x count -= 1 if count == 0: return recover(root.left,count,x,y) recover(root.right,count,x,y) nums = inorder(root) x,y = find_swap(nums) recover(root,2,x,y)

C++版本如下： 需要注意个小问题，C++不能有多个返回值

class Solution { public: void recoverTree(TreeNode* root) { vector<int> nums; inorder(root,nums); vector<int> swapnums = find_swaps(nums); recover(root,swapnums[0],swapnums[1],2); } void inorder(TreeNode* root,vector<int>& nums){ if (!root) return; inorder(root->left,nums); nums.push_back(root->val); inorder(root->right,nums); } vector<int> find_swaps(vector<int>& nums){ int x=-1,y=-1; for (int i=0;i<nums.size()-1;i++){ if (nums[i+1]<nums[i]){ y = nums[i+1]; if (x==-1){ x = nums[i]; }else break; } } // C++不能有多个返回值 return {x,y}; } void recover(TreeNode* root,int x,int y,int count){ if (root){ if (root->val==x || root->val==y){ if (root->val==x){ root->val=y; }else root->val=x; //下面的表达容易错，慎用 // root->val= (root->val==x)?y:x; count --; if (count==0) return; } recover(root->left,x,y,count); recover(root->right,x,y,count); } } };