代码随想录day21 | ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

530. 二叉搜索树的最小绝对差

class Solution {
private:
    int result = INT_MAX;
    TreeNode* pre = NULL;
    void traversal(TreeNode* cur){
        if (cur == NULL)    return;
        traversal(cur->left); //左
        if(pre != NULL){        //中
            result = min(result, cur->val - pre->val);
        }
        pre = cur;
        traversal(cur->right);    //右
    }
public:
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return result;
    }
};

501.二叉搜索树中的众数

class Solution {

private:
    int maxCount = 0;
    int count = 0;
    TreeNode* pre = NULL;
    vector<int> result;

    void searchBST(TreeNode* cur){
        if(cur == NULL) return;

        searchBST(cur->left);   //左

        //中
        if(pre == NULL){
            count = 1;
        }
        else if(pre->val == cur->val){
            count++;
        }
        else{   // pre != NULL && pre->val != cur->val
            count = 1; 
        }
        pre = cur;  //移动指针

        if(count == maxCount){
            result.push_back(cur->val);
        }

        if(count > maxCount){
            maxCount = count;
            result.clear();
            result.push_back(cur->val);
        }

        searchBST(cur->right);  //右
        return;

    }

public:
    vector<int> findMode(TreeNode* root) {
        count = 0;
        maxCount = 0;
        pre = NULL;
        result.clear();

        searchBST(root);
        return result; 
    }
};

236.二叉树的最近公共祖先

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == q || root == p || root == NULL)  return root;
        
        TreeNode* left = lowestCommonAncestor(root->left, p ,q);    //左
        TreeNode* right = lowestCommonAncestor(root->right, p, q);  //右

        //中
        if(left != NULL && right != NULL)   return root;
        if(left == NULL && right != NULL)   return right;
        else if(left != NULL && right == NULL)  return left;
        else{   // (left == NULL && right == NULL)
            return NULL;
        }
    }
};