本文主要是介绍Crack LeetCode 之 99. Recover Binary Search Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://leetcode.com/problems/recover-binary-search-tree/
BST的两个节点被调换了位置，如何恢复？
我们对BST做中序遍历应该得到一个有序序列，但是节点被调换位置的话，中序遍历就会遇到一个节点的前序节点比该节点大的情况，所以我们可以用中序遍历找到位置错误的节点。
节点调换位置有两种情况：一是相邻两个节点被调换；二是不相邻的两个节点被调换。对于前者，中序遍历后只会有一次顺序不对的情况，我们只需要调换这两个节点的位置；对于后者则会有两次顺序不匹配，我们要把第一次顺序不匹配的第一个节点和第二次的第二个节点对调位置。
另外，通过这个练习我们也可以顺便复习一下树的遍历。我找到一个用gif展示树的遍历的网页：http://ceadserv1.nku.edu/longa/classes/mat385_resources/docs/traversal.htm 脑中有这个概念还是挺重要的。
以下代码的时间复杂度是O(n)，空间复杂度是O(1)。
class Solution
{TreeNode* m_pre;vector<TreeNode*> m_res;public:Solution(){m_pre = NULL;}void recoverTree(TreeNode* root){helper(root);if ( m_res.empty() == false ) {int tmp = m_res[1]->val;m_res[1]->val = m_res[0]->val;m_res[0]->val = tmp;}}void helper(TreeNode* root){if(root == NULL)return;helper(root->left);if(m_pre!=NULL && m_pre->val > root->val) {if ( m_res.empty() ) {m_res.push_back(m_pre);m_res.push_back(root);}else {m_res[1] = root;}}m_pre = root;helper(root->right);}
};
class Solution:def __init__(self):self.m_pre = Noneself.m_results = []def recoverTree(self, root):if root is None:returnself.helper( root )if len(self.m_results) != 0:tmp = self.m_results[0].valself.m_results[0].val = self.m_results[1].valself.m_results[1].val = tmpdef helper( self, root ):if root is None:returnself.helper( root.left )if self.m_pre is not None and self.m_pre.val > root.val:if len(self.m_results) == 0:self.m_results.append( self.m_pre )self.m_results.append( root )else:self.m_results[1] = rootself.m_pre = rootself.helper( root.right )
这篇关于Crack LeetCode 之 99. Recover Binary Search Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
