LeetCode & 검 지 혜택: 두 갈래 검색 트 리 시리즈: 두 갈래 검색 트 리, 두 갈래 검색 트 리 의 중 수 를 검증 합 니 다 (중간 순 서 를 이용 하여 해결 합 니 다)

LeetCode 98. 이 진 트 리 검증
이 진 트 리 를 지정 하여 효과 적 인 이 진 트 리 인지 판단 합 니 다.
이 진 트 리 가 다음 과 같은 특징 을 가지 고 있다 고 가정 합 니 다.

노드 의 왼쪽 트 리 는 현재 노드 보다 작은 숫자 만 포함 합 니 다.

노드 의 오른쪽 트 리 는 현재 노드 보다 큰 숫자 만 포함 합 니 다.

모든 왼쪽 나무 와 오른쪽 나무 자체 도 이 진 트 리 여야 합 니 다.

예시 1:
입력:

    2
   /  \
  1    3

출력: true
예제 2: 입력:

 5
/ \
1   4
   / \
  3   6

출력: false 해석: 입력: [5, 1, 4, null, null, 3, 6].뿌리 노드 의 값 은 5 이지 만 오른쪽 노드 의 값 은 4 이다.
문제 풀이 사고: 중간 순서 옮 겨 다 니 기
이 진 트 리 의 특징 에 따라 왼쪽 노드 의 값 을 검색 합 니 다.
코드 구현:

C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        long pre = LONG_MIN;
        return inorder(root,pre);
    }
    bool inorder(TreeNode* root,long &inder){
        if(root == NULL){
            return true;
        }
        if (!inorder(root->left, inder)) {
            return false;
        }
        if(root->val <= inder){
            return false;
        }
        inder = root->val;
        return inorder(root->right,inder);
    }
};

스 택 을 이용 하여 중간 순 서 를 옮 겨 다 닌 다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        long pre = LONG_MIN;
        stack<TreeNode*> stack;
        while (!stack.empty() || root != nullptr) {
            while (root != nullptr) {
                stack.push(root);
                root = root -> left;
            }
            root = stack.top();
            stack.pop();
            //                      inorder，         
            if (root -> val <= pre) return false;
            pre = root -> val;
            root = root -> right;
        }
        return true;
    }
};

LeetCode 501. 이 진 트 리 의 개수 검색
같은 값 을 가 진 이 진 검색 트 리 (BST) 를 지정 하여 BST 의 모든 중 수 를 찾 습 니 다 (주파수 가 가장 높 은 요소 가 나타 납 니 다).
BST 에 다음 과 같은 정의 가 있다 고 가정 합 니 다.

결점 왼쪽 서브 트 리 에 포 함 된 결점 의 값 은 현재 결점 과 같은 값

보다 작다.

결점 오른쪽 서브 트 리 에 포 함 된 결점 의 값 은 현재 결점 과 같은 값

보다 크다.

왼쪽 나무 와 오른쪽 나 무 는 모두 이 진 수색 나무

예 를 들 면:
주어진 BST [1, null, 2, 2],

  1
   \
    2
   /
 2

돌아 가기 [2].
알림: 개수 가 1 개 를 넘 으 면 출력 순 서 를 고려 하지 않 아 도 됩 니 다.
문제 풀이 의 방향 은 위의 문제 와 유사 하고 중 서 를 이용 한 사상 이다.중간 순 서 를 옮 겨 다 니 면 현재 결점 (root) 값 과 전구 결점 (pre) 값 을 각각 비교 할 수 있 습 니 다. 현재 노드 값 의 출현 횟수 (curTimes) 와 최대 출현 횟수 (max Times) 를 업데이트 합 니 다. 규칙 을 업데이트 합 니 다. curTimes = max Times 라면 root - > val 을 결과 벡터 (res) 에 추가 합 니 다. curTimes > max Times, res 를 비우 면 root - > val 을 res 에 추가 하고 max Times 를 curTimes 로 업데이트 합 니 다.
코드 구현 은 다음 과 같 습 니 다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void inorder(TreeNode* root, TreeNode*& pre,int& curTimes, int& maxTimes,vector<int>& res){
        if (!root) return;
        inorder(root->left,pre,curTimes,maxTimes,res);
        if(pre && pre->val == root->val){
            curTimes = curTimes + 1;
        }
        else{
            curTimes = 1;
        }
        if(curTimes == maxTimes){
            res.push_back(root->val);
        }
        if(curTimes>maxTimes){
            maxTimes = curTimes;
            res.clear();
            res.push_back(root->val);
        }
        pre = root;
        inorder(root->right,pre,curTimes,maxTimes,res);
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        TreeNode* pre = NULL;
        int curTimes = 1,maxTimes = 0;
        inorder(root,pre,curTimes,maxTimes,res);
        return res;
    }
};

중간 순 서 를 사용 하여 결점 의 값 을 배열 v 에 저장 한 다음 에 문 제 를 배열 v 의 중수 로 전환시킨다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        int curTimes = 1,maxTimes = 1;
        inorder(root);
        if(vec.size()==0) return res;//         
        res.push_back(vec[0]);//   res  
        for(int i = 1; i < vec.size();i++){
            if(vec[i-1] == vec[i]){
                curTimes += 1;
            }
            else{
                curTimes = 1;
            }
            if(curTimes == maxTimes){
                res.push_back(vec[i]);
            }
            else if(curTimes>maxTimes){
                res.clear();
                maxTimes = curTimes;
                res.push_back(vec[i]);
            }
        }
        return res;

    }
    void inorder(TreeNode* root){
        if(!root){
            return ;
        }
        inorder(root->left);
        vec.push_back(root->val);
        inorder(root->right);
    }
private:
    vector<int> res;
    vector<int> vec;
};