LeetCode 솔루션 분류
99. Recover Binary Search Tree
본문
[ LeetCode 시즌 3 ] 2022년 4월 18일 문제입니다
https://leetcode.com/problems/recover-binary-search-tree/
[Medium] 99. Recover Binary Search Tree
You are given the root
of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
Example 1:
Input: root = [1,3,null,null,2] Output: [3,1,null,null,2] Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.
Example 2:
Input: root = [3,1,4,null,null,2] Output: [2,1,4,null,null,3] Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.
Constraints:
- The number of nodes in the tree is in the range
[2, 1000]
. -231 <= Node.val <= 231 - 1
Follow up: A solution using
O(n)
space is pretty straight-forward. Could you devise a constant O(1)
space solution? 관련자료
-
링크
댓글 1
bobkim님의 댓글
- 익명
- 작성일
Runtime: 36 ms, faster than 74.64% of C++ online submissions for Recover Binary Search Tree.
Memory Usage: 57.8 MB, less than 70.43% of C++ online submissions for Recover Binary Search Tree.
Memory Usage: 57.8 MB, less than 70.43% of C++ online submissions for Recover Binary Search Tree.
class Solution {
public:
TreeNode* p1 = nullptr, *p2 = nullptr, *p_tmp=nullptr;
int tmp=INT_MIN;
void search(TreeNode* p){
if(p==nullptr)
return;
//ascending order
if(p->left != nullptr)
search(p->left);
if(p->val < tmp){
//catch by previous node
if(p1 == nullptr)
p1=p_tmp;
//catch by current node
if(p1 != nullptr)
p2=p;
}
tmp=p->val;
p_tmp=p;
if(p->right != nullptr)
search(p->right);
}
void recoverTree(TreeNode* root){
search(root);
tmp=p1->val;
p1->val=p2->val;
p2->val=tmp;
}
};