99. Recover Binary Search Tree
給定一個二元搜索樹（BST）的根節點，樹中恰好有兩個節點的值被錯誤地交換了。在不改變樹的結構的情況下，恢復樹的正確結構。
範例：
輸入：root = [1,3,null,null,2] 輸出：[3,1,null,null,2] 解釋：3 不應該是 1 的左子節點，因為 3 > 1。交換 1 和 3 使得 BST 變得有效。
Python
class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
# Variables to hold the nodes that need to be swapped
self.firstElement = None
self.secondElement = None
# Variable to keep track of the previous node in in-order traversal
self.prevElement = TreeNode(float('-inf'))
# Helper function to perform in-order traversal and find the swapped nodes
def inorder(node):
if not node:
return
# Traverse the left subtree
inorder(node.left)
# Identify the two swapped nodes
# If the current node is less than the previous node, we potentially have an anomaly
if self.prevElement and self.prevElement.val > node.val:
# The first element is not yet found, set it to prevElement
if not self.firstElement:
self.firstElement = self.prevElement
# Always update the second element to the current node
self.secondElement = node
# Update prevElement to the current node
self.prevElement = node
# Traverse the right subtree
inorder(node.right)
# Start the in-order traversal
inorder(root)
# Swap the values of the first and second elements to correct the tree
self.firstElement.val, self.secondElement.val = self.secondElement.val, self.firstElement.val
16.92MB, 64ms
C++
class Solution {
private:
TreeNode* first = nullptr;
TreeNode* second = nullptr;
TreeNode* prev = nullptr;
void inorderTraversal(TreeNode* root) {
if (root == nullptr) return;
inorderTraversal(root->left);
if (prev != nullptr && root->val < prev->val) {
if (first == nullptr) {
first = prev;
}
second = root;
}
prev = root;
inorderTraversal(root->right);
}
public:
void recoverTree(TreeNode* root) {
inorderTraversal(root);
// Swap the values of the two nodes
if (first != nullptr && second != nullptr) {
int temp = first->val;
first->val = second->val;
second->val = temp;
}
}
};
60.27MB, 16ms
Javascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var recoverTree = function(root) {
let firstElement = null;
let secondElement = null;
let prevElement = new TreeNode(Number.MIN_SAFE_INTEGER); // Use MIN_SAFE_INTEGER as the initial value
// Helper function to perform in-order traversal
function traverse(node) {
if (node === null) return;
// Traverse the left subtree
traverse(node.left);
// Find the first and second elements that are out of the normal order
if (firstElement === null && prevElement.val > node.val) {
firstElement = prevElement;
}
if (firstElement !== null && prevElement.val > node.val) {
secondElement = node;
}
prevElement = node; // Update prevElement to the current node
// Traverse the right subtree
traverse(node.right);
}
// Perform the in-order traversal to find the misplaced nodes
traverse(root);
// Swap the values of the first and second element to correct the tree
let temp = firstElement.val;
firstElement.val = secondElement.val;
secondElement.val = temp;
};
60.27MB, 16ms
