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 = None


class 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