[LeetCode] 99. Recover Binary Search Tree

Problem : https://leetcode.com/problems/recover-binary-search-tree/

O(N) space solution:

1) In-order traverse the tree and put node values in to an array

2) Sort the array

3) In-order traverse the tree and set node values with the sorted array

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        
        def inorder_get(node, values):
            if node:
                inorder_get(node.left, values)
                values.append(node.val)
                inorder_get(node.right, values)
        
        def inorder_set(node, values, i):
            if node:
                i = inorder_set(node.left, values, i)
                
                node.val = values[i]
                i += 1
                
                i = inorder_set(node.right, values, i)
            
            return i
        
        values = []
        
        inorder_get(root, values)
        values.sort()
        inorder_set(root, values, 0)