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.
1var recoverTree = function(root) {
2 const nodes = [];
3 inorder(root, nodes);
4 let first = null, second = null;
5 for (let i = 0; i < nodes.length - 1; i++) {
6 if (nodes[i].val > nodes[i + 1].val) {
7 second = nodes[i + 1];
8 if (!first) first = nodes[i];
9 else break;
10 }
11 }
12 [first.val, second.val] = [second.val, first.val];
13};
14function inorder(node, nodes) {
15 if (!node) return;
16 inorder(node.left, nodes);
17 nodes.push(node);
18 inorder(node.right, nodes);
19}The JavaScript solution mirrors the logic used in the other languages: using an array to assemble tree nodes into a sequence, locating misplaced elements, and adjusting node values to reconstruct the valid 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).
public void RecoverTree(TreeNode root) {
TreeNode first = null, second = null, prev = null;
TreeNode current = root;
while (current != null) {
if (current.left == null) {
if (prev != null && current.val < prev.val) {
second = current;
if (first == null) first = prev;
}
prev = current;
current = current.right;
} else {
TreeNode pre = current.left;
while (pre.right != null && pre.right != current) pre = pre.right;
if (pre.right == null) {
pre.right = current;
current = current.left;
} else {
pre.right = null;
if (prev != null && current.val < prev.val) {
second = current;
if (first == null) first = prev;
}
prev = current;
current = current.right;
}
}
}
int temp = first.val;
first.val = second.val;
second.val = temp;
}
}This C# solution follows the Morris Traversal strategy, minimizing space usage by recompensing tree structure for the necessity of stack memory. It directly handles tree sequencing and discovers anomalies during traversal.