LeetCode解题之Recover Binary Search Tree
原题
一棵二叉搜索树中的两个节点交换了位置，找出并调整。
注意点：
- 最好仅仅用常量的空间
样例：
输入:
3 / \1 2
输出:
2 / \1 3
解题思路
二叉搜索树的中序遍历能够使它的节点排列成一个递增的序列，那就能够把问题简化成在一个递增序列中有两个元素交换了位置。而前面的元素大于后面的元素表示顺序出错，假设整个序列就一处这种问题，那仅仅要交换这两个元素。假设有两处。在仅仅有两个元素顺序有问题的前提下，应该交换第一次错位的前元素（大的元素应该往后放）与第二次错位的后元素（小元素往前放）。
AC源代码
# Definition for a binary tree node.class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution(object): def __init__(self): self.node1 = None self.node2 = None self.pre = None def recoverTree(self, root): """ :type root: TreeNode :rtype: void Do not return anything, modify root in-place instead. """ self.__scan(root) self.node1.val, self.node2.val = self.node2.val, self.node1.val def __scan(self, root): if root is None: return self.__scan(root.left) if self.pre is not None: if root.val < self.pre.val: if self.node1 is None: self.node1 = self.pre self.node2 = root else: self.node2 = root self.pre = root self.__scan(root.right)if __name__ == "__main__": None
欢迎查看我的 () 来获得相关源代码。