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.
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;
    }
};
LeetCode 솔루션 357 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0