LeetCode 题解（98）: Recover Binary Search Tree

本文主要是介绍LeetCode 题解（98）: Recover Binary Search Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

wo elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O( n) space is pretty straight forward. Could you devise a constant space solution?

题解：

不用O(n) space也很简单， 如果中序遍历的话，二叉搜索树应该是递增序列，所以只要找到值减小的位置即可。C++使用了指针的指针，Java和Python使用了一个wrapper class。但其实只用定义类变量即可。切记。

c++版：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:void recoverTree(TreeNode* root) {TreeNode* first = NULL;TreeNode* second = NULL;TreeNode* pre = NULL;traverse(root, &pre, &first, &second);int tmp = first->val;first->val = second->val;second->val = tmp;}void traverse(TreeNode* root, TreeNode** pre, TreeNode** first, TreeNode** second) {if(root->left != NULL) {traverse(root->left, pre, first, second);}if(*pre != NULL && (*pre)->val > root->val) {if(*first == NULL) {*first = *pre;*second = root;}else*second = root;*pre = root;} else {*pre = root;}if(root->right != NULL) {traverse(root->right, pre, first, second);}}
};

Java版：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class TreeNodeWrapper {TreeNode node;TreeNodeWrapper() {node = null;}
} public class Solution {public void recoverTree(TreeNode root) {TreeNodeWrapper pre = new TreeNodeWrapper();TreeNodeWrapper first = new TreeNodeWrapper();;TreeNodeWrapper second = new TreeNodeWrapper();;traverse(root, pre, first, second);int temp = first.node.val;first.node.val = second.node.val;second.node.val = temp;}void traverse(TreeNode root, TreeNodeWrapper pre, TreeNodeWrapper first, TreeNodeWrapper second) {if(root.left != null)traverse(root.left, pre, first, second);if(pre.node != null && pre.node.val > root.val) {if(first.node == null) {first.node = pre.node;}second.node = root;}pre.node = root;if(root.right != null)traverse(root.right, pre, first, second);}
}

Python版：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class TreeNodeWrapper:def __init__(self):self.node = Noneclass Solution:# @param {TreeNode} root# @return {void} Do not return anything, modify root in-place instead.def recoverTree(self, root):pre, first, second = TreeNodeWrapper(), TreeNodeWrapper(), TreeNodeWrapper()self.traverse(root, pre, first, second)tmp = first.node.valfirst.node.val = second.node.valsecond.node.val = tmpdef traverse(self, root, pre, first, second):if root.left != None:self.traverse(root.left, pre, first, second)if pre.node != None and pre.node.val > root.val:if first.node == None:first.node = pre.nodesecond.node = rootpre.node = rootif root.right != None:self.traverse(root.right, pre, first, second)

这篇关于LeetCode 题解（98）: Recover Binary Search Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---