897. 증가 순서 찾기 트리

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
	def __init__(self):
		self.ans = None
		self.current = None
	
	
	def increasingBST(self, root, tail = None):
		def inOrder(node):
			if node == None:
				return
			inOrder(node.left)
			if self.ans == None:
				self.ans = node
				self.current = node
			else:
				self.current.right = node
				self.current = node
			self.current.left = None
			inOrder(node.right)
		
		inOrder(root)
		return self.ans

    def increasingBST(self, root, tail = None):
        
        # if this null node was a left child, tail is its parent
        # if this null node was a right child, tail is its parent's parent
        if not root: return tail

        # recursive call, traversing left while passing in the current node as tail
        res = self.increasingBST(root.left, root)

        # we don't want the current node to have a left child, only a single right child
        root.left = None

        # we set the current node's right child to be tail
        # what is tail? this part is important
        # if the current node is a left child, tail will be its parent
        # else if the current node is a right child, tail will be its parent's parent
        root.right = self.increasingBST(root.right, tail)

        # throughout the whole algorithm, res is the leaf of the leftmost path in the original tree
        # its the smallest node and thus will be the root of the modified tree
        return res