LeetCode 솔루션

99. Recover Binary Search Tree

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.04.18 17:52

7,111 조회
1 댓글
0 추천
0 비추천
목록 게시글 쓰기

[ 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?

#LeetCode, #문제풀이, #시즌3, #medium, #Amazon, #Microsoft, #Apple, #Google, #Adobe, #Tree, #Depth-First Search(DFS), #Binary Search Tree(BST), #Binary Tree

링크

https://leetcode.com/problems/recover-binary-search-tree/ 1370 회 연결

익명
작성일 2022.04.20 00:08

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;
    }
};