Question: https://oj.leetcode.com/problems/recover-binary-search-tree/
Question Name: Recover Binary Search Tree
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | # Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param root, a tree node # @return a tree node def recoverTree(self, root): ''' The solution is similar with the in-order travel. We need to find out the rule-breaker, whose value is greater than its successor. Then we need to find out the last node, whose value is smaller that the rule- breaker's. Finanly, we will exchange the value of these two nodes. ''' if root == None: return root stack = [root] previous = None current = root.left toExchangeLeft, toExchangeRight = None, None while len(stack) != 0 or current != None: while current != None: stack.append(current) current = current.left current = stack.pop() if previous != None: if toExchangeLeft == None: # Find the rule-breaker, whose value is greater # then its successor. if previous.val > current.val: toExchangeLeft = previous else: # Find the last node, whose value is smaller # than the rule-breaker. if current.val > toExchangeLeft.val: toExchangeRight = previous break previous = current current = current.right # We checked the all the nodes except the last one. If we did not # find one to be exchanged with the rule-break, the last node # will be used. if toExchangeRight == None: toExchangeRight = previous toExchangeLeft.val, toExchangeRight.val = toExchangeRight.val, toExchangeLeft.val return root |