Sponsored
Sponsored
This approach uses an additional list to store the nodes during an in-order traversal of the BST. The in-order traversal yields the values of the BST in a sorted manner for a correct BST configuration. If two nodes have been swapped, this sorted order will be violated in exactly two places. By storing all nodes during traversal and comparing them, we can identify the two swapped nodes. Once identified, we swap their values to correct the tree.
This method requires O(n) space to store the nodes' values where n is the number of nodes in the tree.
Time Complexity: O(n) since we are conducting an in-order traversal of the tree.
Space Complexity: O(n) as we store nodes in a list for comparison.
This Python solution performs an in-order traversal of the BST and stores the nodes in a list. It then iterates through this list to find the two nodes that are out of order, i.e., the swapped nodes, by checking where the current node value is less than the previous node value. Finally, it swaps the values of these nodes to correct the BST.
This approach leverages Morris Traversal to achieve O(1) space complexity, without needing an auxiliary stack or recursion. Morris Traversal utilizes the tree structure itself to keep track of nodes and ensures the tree is reset to its original configuration after traversal. To correct the BST, we detect swapped nodes by identifying violation of BST properties during traversal, and then we swap these nodes to achieve a valid BST.
Time Complexity: O(n).
Space Complexity: O(1).
1class Solution:
2 def recoverTree(self, root: TreeNode) -> None:
3 first = second = prev = None
4 current = root
5 while current:
6 if current.left is None:
7 if prev and current.val < prev.val:
8 second = current
9 if first is None:
10 first = prev
11 prev = current
12 current = current.right
13 else:
14 pre = current.left
15 while pre.right and pre.right != current:
16 pre = pre.right
17 if pre.right is None:
18 pre.right = current
19 current = current.left
20 else:
21 pre.right = None
22 if prev and current.val < prev.val:
23 second = current
24 if first is None:
25 first = prev
26 prev = current
27 current = current.right
28 first.val, second.val = second.val, first.valThis Python solution uses Morris Inorder Traversal, which leverages the threads in the tree structure to avoid using additional space. While traversing, we establish temporary links (threads) to visiting nodes using their predecessor relations. We detect unordered node pairs and correct them by swapping their values.