1
# Runtime: 61 ms (Top 95.6%) | Memory: 16.68 MB (Top 75.1%)
2

3

4
class Solution:
5
    """
6
    Brute force kind of thing
7
    -> Inorder Traversal returns sorted array
8
    -> find a swap btwn numbers to make sorted
9
    Make single swap to make array sorted
10
    [1, 2, 3, 4, 10, 6, 9, 5, 10, 12]
11
     x, x, x, x, x, No
12
        prev number is mismatch -> 10 is cause
13
    now go frm right to left
14
    [1, 2, 3, 4, 10, 6, 9, 5, 11, 12]
15
                        No x   x   x
16
                    mismatch with next number -> 5 is the cause
17
    swap 10, 5
18

19
    Eg: 2
20
    [3, 2, 1]
21
     x  No -> 3 is the cause
22
    [3, 2, 1]
23
     x  No -> 1 is the cause
24
    swap values -> 1, 3
25
    """
26

27
    def inorder(self, root, li):
28
        if root is None:
29
            return li
30
        li = self.inorder(root.left, li)
31
        li.append(root)
32
        li = self.inorder(root.right, li)
33
        return li
34

35
    def recoverTree(self, root: TreeNode) -> None:
36
        """
37
        Do not return anything, modify root in-place instead.
38
        """
39
        li = self.inorder(root, [])
40
        n = len(li)
41
        i, j = 1, n - 2
42
        a = li[0]
43
        for i in range(1, n):
44
            if li[i].val < li[i - 1].val:
45
                a = li[i - 1]
46
                break
47
        b = li[-1]
48
        for i in range(n - 2, -1, -1):
49
            if li[i].val > li[i + 1].val:
50
                b = li[i + 1]
51
                break
52

53
        a.val, b.val = b.val, a.val