# Python inOrderTraversal O(n)

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

class Solution(object):

def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""

def inorderTraversal(node):
if node is None:
return []

return inorderTraversal(node.left) + [node] + inorderTraversal(node.right)

def switch(n1, n2):
n1.left, n1.right, n2.left, n2.right = n2.left, n2.right, n1.left, n1.right
return

q = inorderTraversal(root)
pairs = []
i = 0
while i < len(q)-1:
if q[i].val > q[i+1].val:
pairs.append(i)
i += 1

if len(pairs) == 1:
i = pairs[0]
n1, n2 = q[i], q[i+1]
elif len(pairs) == 2:
i, j = pairs
n1, n2 = q[i], q[j+1]
n1.val, n2.val = n2.val, n1.val

return
``````

Inorder Traversal, find the incorrect pairs. Switch the values. Done

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.