###### tags: `Leetcode` `medium` `tree` `python`

# 99. Recover Binary Search Tree

## [題目連結:] https://leetcode.com/problems/recover-binary-search-tree/

## 題目:
You are given the ```root``` of a binary search tree (BST), where the values of **exactly** two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.


#### [圖片來源:] https://leetcode.com/problems/recover-binary-search-tree/

## 解題想法:
* 題目為給一BST，恰好兩node的值錯誤，求將兩node的值交換
* 利用inorder traversal:
* 因為BST在inorder時候順序是由小到大，因此找到不符合的兩點交換彼此的值即可
* inorder:
* pre: 紀錄前一個node
* first: 紀錄第一個問題node
* second: 紀錄第二個問題node
* 每次判斷pre.val是否小於當前root.val:
* 若小於表示正常
* 大於表示有問題:
* 若first還沒賦值，
* 則first=pre
* 否則不用更新
* second一律=當前root
* 流程:

ex:
1   2   3   4   5   6
若為
1   5   3   4   2   6
當root=3 pre=5 pre>5 所以將first設為pre=5  second=3
繼續跑:
再遇到錯誤 root=2 pre=4 此時first有值了 更新second就好
將second更新為root=2
最後first=5、second=2即為內奸

## Python:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root = self
        stack=[root]
        flag = 1
        while stack:
            root=stack.pop(0)
            if flag==1:
                print(root.val,end='')
                flag=0
            if root.left:
                print('->',root.left.val,end='')
                stack.append(root.left)
            if root.right:
                print('->',root.right.val,end='')
                stack.append(root.right)
        print('\n')

class Solution(object):
    def recoverTree(self,root):
        #想法: bst在inorder時順序是由小到大 因此找到不符合的兩點交換即可
        self.pre = None
        self.first=None
        self.second=None
        self.inorder(root)
        self.first.val,self.second.val = self.second.val,self.first.val
        
    def inorder(self,root):
        if not root:
            return
        self.inorder(root.left)

        #按理說pre.val應該要比現在的root.val小
        if self.pre and self.pre.val>root.val:
            #第一次找到錯pre>root的，值要選pre為first
            if not self.first:
                self.first=self.pre
            #第二次找到錯的pre>root，值要選root為second
            self.second=root
        self.pre = root
        self.inorder(root.right)

root = TreeNode(3)
root.insertLeft(1)
root.insertRight(4)
root.right.insertLeft(2)
root.printTree()

result = Solution()
result.recoverTree(root)
root.printTree()
#print(ans)