C++LeetCode 구현(99.이 진 트 리 복원)

[LeetCode]99.이 진 검색 트 리 복구 이 진 검색 트 리 복원
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Example 1:
Input: [1,3,null,null,2]
   1
/
3
\
2
Output: [3,1,null,null,2]
   3
/
1
\
2
Example 2:
Input: [3,1,4,null,null,2]
3
/ \
1   4
/
2
Output: [2,1,4,null,null,3]
  2
/ \
1   4
/
3
Follow up:

A solution using O(n) space is pretty straight forward.

Could you devise a constant space solution?

이 문 제 는 이 진 트 리 를 복원 하 라 고 요구 합 니 다.그 중에서 두 개의 순서 가 바 뀌 었 다 고 합 니 다.문 제 는 O(n)의 해법 이 직관 적 이 라 고 합 니 다.이런 해법 은 재 귀 를 사용 하고 중간 순서 로 나 무 를 옮 겨 다 니 며 모든 노드 를 1 차원 벡터 에 저장 하고 모든 노드 값 을 다른 1 차원 벡터 에 저장 한 다음 에 저장 절 점 값 의 1 차원 벡터 에 정렬 해 야 합 니 다.배열 한 배열 을 순서대로 노드 에 부여 합 니 다.이런 가장 일반적인 해법 은 임의의 수의 노드 가 어 지 러 운 상황 에 대해 먼저 이런 해법 을 붙 일 수 있다.
해법 1:

// O(n) space complexity
class Solution {
public:
    void recoverTree(TreeNode* root) {
        vector<TreeNode*> list;
        vector<int> vals;
        inorder(root, list, vals);
        sort(vals.begin(), vals.end());
        for (int i = 0; i < list.size(); ++i) {
            list[i]->val = vals[i];
        }
    }
    void inorder(TreeNode* root, vector<TreeNode*>& list, vector<int>& vals) {
        if (!root) return;
        inorder(root->left, list, vals);
        list.push_back(root);
        vals.push_back(root->val);
        inorder(root->right, list, vals);
    }
};

그 다음 에 블 로 거들 은 인터넷 에서 많은 다른 해법 을 찾 아 보 았 다.다른 하 나 는 1 차원 벡터 를 이중 포인터 로 대체 하 는 것 을 보 았 다.그러나 이런 방법 은 재 귀 를 사 용 했 고 O(1)공간 복잡 도의 해법 도 아니 었 다.여 기 는 세 개의 지침 이 필요 하 다.first,second 는 각각 첫 번 째 와 두 번 째 어 지 러 운 위 치 를 나타 내 는 노드 를 사용 했다.pre 는 현재 노드 의 중간 순서 가 옮 겨 다 니 는 앞의 노드 를 가리킨다.여 기 는 전통 적 인 중간 순서 로 재 귀 를 옮 겨 다 니 지만 노드 값 을 출력 해 야 하 는 곳 에서 pre 와 현재 노드 값 의 크기 를 판단 하 는 것 으로 바 뀌 었 습 니 다.pre 가 크 면 first 가 비어 있 으 면 first 는 pre 가 가리 키 는 노드 를 가리 키 고 second 를 현재 노드 를 가리 킵 니 다.이렇게 해서 전체 나 무 를 옮 겨 다 니 며 first 와 second 가 존재 하면 노드 값 을 교환 하면 됩 니 다.이 알고리즘 의 공간 복잡 도 는 여전히 O(n)이 고 n 은 나무의 높이 입 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

// Still O(n) space complexity
class Solution {
public:
    TreeNode *pre = NULL, *first = NULL, *second = NULL;
    void recoverTree(TreeNode* root) {
        inorder(root);
        swap(first->val, second->val);
    }
    void inorder(TreeNode* root) {
        if (!root) return;
        inorder(root->left);
        if (!pre) pre = root;
        else {
            if (pre->val > root->val) {
                if (!first) first = pre;
                second = root;
            }
            pre = root;
        }
        inorder(root->right);
    }
};

우 리 는 사실 중 서 를 옮 겨 다 니 기 때문에 교체 하 는 쓰기 도 사용 할 수 있다.  Binary Tree Inorder Traversal  또한 스 택 을 통 해 이 루어 질 수 있 습 니 다.원 리 는 앞의 것 과 같 습 니 다.앞의 노드 를 기록 하고 현재 노드 에 비해 앞의 노드 값 이 크 면 first 와 second 를 업데이트 하고 마지막 으로 first 와 second 의 노드 값 을 교환 하면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 3:

// Always O(n) space complexity
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *pre = NULL, *first = NULL, *second = NULL, *p = root;
        stack<TreeNode*> st;
        while (p || !st.empty()) {
            while (p) {
                st.push(p);
                p = p->left;
            }
            p = st.top(); st.pop();
            if (pre) {
                if (pre->val > p->val) {
                    if (!first) first = pre;
                    second = p;
                }
            }
            pre = p;
            p = p->right;
        }
        swap(first->val, second->val);
    }
};

이 문제 의 진정 으로 요구 에 부합 되 는 해법 은 Morris 를 옮 겨 다 니 는 것 이다.이것 은 재 귀적 이지 않 고 스 택 을 사용 하지 않 으 며 공간 복잡 도 는 O(1)의 옮 겨 다 니 는 방법 으로 블 로 거 이전의 블 로 그 를 참조 할 수 있다.  Binary Tree Inorder Traversal이 를 바탕 으로 수정 을 하고 first,second 와 parent 지침 을 추가 하여 현재 노드 값 과 중간 순서 가 옮 겨 다 니 는 앞의 점 값 의 크기 를 비교 합 니 다.위의 재 귀 알고리즘 과 사고 가 비슷 합 니 다.코드 는 다음 과 같 습 니 다.
해법 4:

// Now O(1) space complexity
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *first = nullptr, *second = nullptr, *cur = root, *pre = nullptr ;
        while (cur) {
            if (cur->left){
                TreeNode *p = cur->left;
                while (p->right && p->right != cur) p = p->right;
                if (!p->right) {
                    p->right = cur;
                    cur = cur->left;
                    continue;
                } else {
                    p->right = NULL;
                }  
            }
            if (pre && cur->val < pre->val){
              if (!first) first = pre;
              second = cur;
            }
            pre = cur;
            cur = cur->right;
        }
        swap(first->val, second->val);
    }
};

C++구현 LeetCode(99.이 진 검색 트 리 복원)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++복원 이 진 검색 트 리 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 도 많은 응원 부탁드립니다!