LeetCode Solutions
class Solution {
public:
void recoverTree(TreeNode* root) {
inorder(root);
swap(x, y);
}
private:
TreeNode* pred = nullptr;
TreeNode* x = nullptr; // 1st wrong node
TreeNode* y = nullptr; // 2nd wrond node
void inorder(TreeNode* root) {
if (root == nullptr)
return;
inorder(root->left);
if (pred && root->val < pred->val) {
y = root;
if (x == nullptr)
x = pred;
else
return;
}
pred = root;
inorder(root->right);
}
void swap(TreeNode* x, TreeNode* y) {
const int temp = x->val;
x->val = y->val;
y->val = temp;
}
};
|
class Solution {
public void recoverTree(TreeNode root) {
inorder(root);
swap(x, y);
}
private TreeNode pred = null;
private TreeNode x = null;
private TreeNode y = null;
private void inorder(TreeNode root) {
if (root == null)
return;
inorder(root.left);
if (pred != null && root.val < pred.val) {
y = root;
if (x == null)
x = pred;
else
return;
}
pred = root;
inorder(root.right);
}
private void swap(TreeNode x, TreeNode y) {
final int temp = x.val;
x.val = y.val;
y.val = temp;
}
}
|
class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
def swap(x: Optional[TreeNode], y: Optional[TreeNode]) -> None:
temp = x.val
x.val = y.val
y.val = temp
def inorder(root: Optional[TreeNode]) -> None:
if not root:
return
inorder(root.left)
if self.pred and root.val < self.pred.val:
self.y = root
if not self.x:
self.x = self.pred
else:
return
self.pred = root
inorder(root.right)
inorder(root)
swap(self.x, self.y)
pred = None
x = None # 1st wrong node
y = None # 2nd wrong node
|
