leetcode의 두 갈래 트리류의 두 갈래 트리 중 순서대로 운용-----OJ173/230/98/99/285 두 갈래 트리 교체기/BST 제K소원소/BST 합법성 여부 판단/BST/두 갈래 트리 다음 노드 회복

본고는 두 갈래 나무의 반복적인 운용에 관한 몇 가지 문제이다
1, OJ173 두 갈래 트리 교체기
핵심은next,hasnext 두 가지 방법을 실현하는 것이다. 사실은 중서 역행에 해당하지만 한 가지 방법으로 나타나도록 요구한다
hasnext를 실현해야 하기 때문에 매번 판단이 번거롭기 때문에 좋은 방법은 다음과 같다.
1. 처음에 비귀속 중서가 돌아다니는 것처럼 왼쪽 나무는 빈 공간이 눌러지지 않을 때까지 창고를 멈추지 않는다
이후:
2,hasnext는 stk가 비어 있는지 판단하면 된다
3. 넥스트는 팝업에서 하나를 꺼내면 된다. 매번 팝업 후 팝업 노드에 오른쪽 트리가 존재한다면 1을 진행한다. 즉, 오른쪽 트리를 창고 왼쪽 노드에 멈추지 않고 눌러 넣지 못할 때까지
이것은 가장 편리하고 합리적인 방식이다. 매번 하나를 꺼내서 판단하지 마라. 그러면 매우 번거롭고 실수하기 쉽다
OJ173 코드:

class BSTIterator {
public:
    stack stk;
    
    BSTIterator(TreeNode *root) {
        while (root) {
            stk.push(root);
            root = root->left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !stk.empty();
    }

    /** @return the next smallest number */
    int next() {
        int v;
        if (!stk.empty()) {
            TreeNode *cur = stk.top();
            stk.pop();
            v = cur->val;
            if (cur->right) {
                cur = cur->right;
                while (cur) {
                    stk.push(cur);
                    cur = cur->left;
                }
            }
            return v;
        }
    }
};

2. OJ230은 두 갈래 나무의 K번째 작은 원소value를 검색합니다
중서 역력의 질서성에 근거하여 본 문제는 전형적인 중서 역력이다
OJ230 코드:

class Solution {
public:
    void helper (TreeNode *cur, int &k, int &res) {
        if (cur) {
            helper(cur->left, k, res);
            if (k == 1) {
                res = cur->val;
            }
            --k;
            helper(cur->right, k, res);
        }
    }
    
    int kthSmallest(TreeNode* root, int k) {
        int res;
        helper(root, k, res);
        return res;
    }
};

3, OJ99 복구 검색 두 갈래 나무
두 갈래 트리를 검색하는 두 노드가value로 바뀌는데 핵심 사고방식은 중서열의 질서성을 이용하여 중서열이 어떤 부분을 어지럽혔는지 보고 어느 두 노드가 바뀌었는지 판단하는 것이다.
구체적으로 생각하면 다음과 같다.
1. 교환된 두 노드는 인접할 수도 있고 인접하지 않을 수도 있다. 그러나 인접하든 안 하든 그 중에서 현재 노드value>= 이전 노드value를 반복해서 발견할 때 이전 노드에 분명히 문제가 있고 현재 노드에도 문제가 있을 수 있음을 설명한다. 이때 이 두 문제 노드를 기록한다.반드시 두 개의 문제 노드를 동시에 기록해야 한다. 왜냐하면 인접 노드가 서로 바뀔 때 바로 인접 두 노드이기 때문이다.인접하지 않은 노드가 교환될 경우 현재 노드와 무관합니다.
2. 그리고 계속해서 중순으로 훑어보고 현재 노드value>= 이전 노드value를 발견하면 교환된 두 노드를 찾을 수 있습니다.만약 다시 문제 노드를 찾지 못한다면 문제가 발생한 것은 최초로 기록된 두 개의 문제 노드, 즉 교환된 것은 두 개의 인접한 노드이다.
따라서 프로그램이 중간 순서로 반복될 때 이전 노드를 얻으려면 인용을 전달해야 한다.또한 중차 귀속 함수는 두 문제 노드의 인용을 전송하고 중차 반복이 끝난 후에 이 두 노드value를 교환하면 된다.
OJ99 코드:

class Solution {
public:
    void helper (TreeNode *cur, TreeNode *&pre, TreeNode *&wrong1, TreeNode *&wrong2) {
        if (cur) {
            helper(cur->left, pre, wrong1, wrong2);
            if (pre) {
                if (cur->val <= pre->val) {
                    if (!wrong1) {
                        wrong1 = pre;
                        wrong2 = cur;
                    } else {
                        wrong2 = cur;
                    }
                }
            }
            pre = cur;
            helper(cur->right, pre, wrong1, wrong2);
        }
    }
    
    void recoverTree(TreeNode* root) {
        if (!root) {
            return;
        }
        
        TreeNode *pre = nullptr, *wrong1 = nullptr, *wrong2 = nullptr;
        helper(root, pre, wrong1, wrong2);
        if (wrong1 && wrong2) {
            int v = wrong1->val;
            wrong1->val = wrong2->val;
            wrong2->val = v;
        }
    }
};

4, OJ285에서 다음 노드를 반복
OJ173 방식
5、OJ98 validate binary search tree
한 개의 두 갈래 나무가 합법적인 검색 두 갈래 나무인지 아닌지를 판단하려면 주의해야 한다. 이 문제는 간단한 순서로 현재 노드와 그 좌우 노드의 크기 관계를 반복해서 판단하면 안 된다. 왜냐하면 하위 나무 아래에 직계가 아닌 갱신된 노드가 크기 관계에 부합되지 않는 상황이 존재하기 때문이다. 예를 들어 뿌리 점은 10이고 오른쪽 노드는 15이며 오른쪽 노드의 왼쪽 노드는 6이다.
이때 중서적 반복파가 쓸모가 있다. 즉, 중서적 반복 서열이 앞수보다 작고 같은 상황이 발생했는지 판단하는 것이다.
OJ98 코드:

class Solution {
public:
    void helper (TreeNode *cur, TreeNode *&prev, bool &res) {
        if (cur) {
            helper(cur->left, prev, res);
            if (prev) {
                if (prev->val >= cur->val) {
                    res = false;
                }
            }
            prev = cur;
            helper(cur->right, prev, res);
        }
    }
    
    bool isValidBST(TreeNode* root) {
        bool res = true;
        if (!root) {
            return res;
        }
        
        TreeNode *prev = nullptr;
        helper(root, prev, res);
        return res;
    }
};