최대 두 갈래 검색 하위 트리 문제

[제목]
두 갈래 나무가 있는데 그 중 모든 노드의 값이 다르다. 노드가 가장 많은 검색 두 갈래 나무를 찾아서 이 나무의 머리 노드로 돌아간다.두 갈래 나무의 머리 결점 루트를 지정하면 원하는 머리 결점을 되돌려주십시오. 여러 노드가 가장 많은 하위 나무가 나타나면 머리 결점 권한 값이 가장 큰 것을 되돌려줍니다.
[분석]
최대 두 갈래로 하위 트리를 검색합니다. 우리는 세 가지 변수를 사용하여 각 결점이 뿌리인 하위 트리의min,max, 그리고 그에 대응하는 최대 두 갈래로 하위 트리의 결점 수를 저장할 수 있습니다.업데이트 여부를 판단하면 됩니다.
주의: (왼쪽 부분의 최대값은lmax로, 오른쪽 부분의 최소값은rmin으로, t는 현재 루트 노드를 나타낸다)

만약lmaxval

만약에 1을 만족시키지 못하면 좌우의 수량이 가장 큰 것을 찾아서 되돌아오면 된다. 계속 찾아서 갱신 여부를 판단한다

[코드]

class MaxSubtree {
public:
    TreeNode* getMax(TreeNode* root) {
        assert(root != nullptr);
        vector res(3, 0); 
        return get_max_detail(root, res);
    }
private:
    TreeNode* get_max_detail(TreeNode* t, vector& res){
        if(t == nullptr){ //res[0] means min, res[1] means max, res[2] means counter of BST tree node
            res[0] = INT_MAX;
            res[1] = INT_MIN;
            res[2] = 0;
            return nullptr;
        }
        
        int lmin = 0, lmax = 0, lcnt = 0;
        TreeNode* lnode = get_max_detail(t->left, res);
        lmin = res[0];
        lmax = res[1];
        lcnt = res[2];
           
        TreeNode* rnode = get_max_detail(t->right, res);
        
        //don't do like (lnode==null && rnode==null) || (lmaxval && rmax>t->val)
        //because the lnode or rnoe maybe not the child of the "t".
        if((lnode == t->left && rnode == t->right) 
           && (lmax < t->val && res[0] > t->val)){    //update
            res[0] = std::min(lmin, t->val);
            res[1] = std::max(res[1], t->val);
            res[2] = lcnt + res[2] + 1;
            return t;
        }
        
        if(lcnt > res[2]){
            //res[0] = lmin;    //this line deleted is also ok
            //res[1] = lmax;   //this line deleted is also ok
            res[2] = lcnt;
            return lnode;
        }
        else
            return rnode;
    }
};

이 문제의 난점은 잎사귀 결점의 상황이다. 처음에 내가 처리한 방식은 그림 주석과 같은 상황이었다. 만약에 최대 두 갈래 검색 서브나무가 연속적이지 않다면 최대 두 갈래 검색 서브나무가 어떤 결점 1에서 끊어졌을 것이다. 아마도 당시 가장 큰 두 갈래 검색 서브나무는 결점 1의 왼쪽 아이가 가지고 있는 서브나무 X(결점 1을 포함하지 않음)를 고려하지 않고 뿌리로 거슬러 올라간 후에또 다른 오른쪽 지점의 최대 두 갈래가 하위 트리 Y를 검색합니다. 뿌리의 아버지가 결점 1이 아닙니다. 이때 하위 트리 X의 최대 값이 val<하위 트리 Y의 최소 값이면
이렇게 해서 끊어진 점과 중간에 여러 개의 불연속적인 점을 포함하는 새로운 최대 두 갈래 검색 트리를 새로 합성하는 것은 잘못된 것입니다!
그래서 (lnode=t->left & & rnode=t->right &...)판단 조건으로 삼다.
주의해야 할 것은 마지막으로 두 마디는 지울 수 있다는 것이다.그런 상황이 생기면 단층이 생기는 것과 같다.앞으로는 그것들의 수를 비교하기만 하면 되고, 그것들의min과max에는 관심이 없다.