代码随想录day21

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

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

? ? ? ? 1.用数组保存二叉树的值

? ? ? ? 遇到搜索二叉树的题可以考虑用一个数组进行保存，因为其中序遍历是有序的。

class Solution {
public:
    vector<int> ans;
    void dfs(TreeNode *root){
        if(root==nullptr) return;
        dfs(root->left);
        ans.push_back(root->val);
        dfs(root->right);
    }
    int getMinimumDifference(TreeNode* root) {
        //用数组记录终止序列，再找出最小绝对值之差
        dfs(root);
        int mmin=INT_MAX;
        for(int i=0;i<ans.size()-1;++i){
            if(mmin>(ans[i+1]-ans[i])){
                mmin=ans[i+1]-ans[i];
            }
        }
        return mmin;
    }
};

? ? ? ? 2.用一个指针pre指向前驱

? ? ? ? ?由于二叉搜索树中序是一个有序序列，因此只需要用pre指针指向前驱，然后进行中序遍历进行判断相邻节点的差就行。

class Solution {
public:
    int ans=INT_MAX;
    TreeNode* pre=nullptr;//指向前驱
    void travel(TreeNode* cur){
        if(cur==nullptr) return;
        travel(cur->left);
        if(pre!=nullptr){
            ans=min(ans,cur->val-pre->val);
        }
        pre=cur;
        travel(cur->right);
    }
    int getMinimumDifference(TreeNode* root) {
        travel(root);
        return ans;
    }
};

501.二叉搜索树中的众数?

?给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

• 结点左子树中所含结点的值小于等于当前结点的值
• 结点右子树中所含结点的值大于等于当前结点的值
• 左子树和右子树都是二叉搜索树

? ? ? ? 1.数组

class Solution {
public:
    vector<int> answer;
    int base,count,maxcount;
    void update(int x){
        if(x==base){
            ++count;
        }else{
            count=1;
            base=x;
        }
        if(count==maxcount){
            answer.push_back(base);
        }
        if(count>maxcount){
            maxcount=count;
            answer=vector<int> {base};
        }
    }
    void dfs(TreeNode* root){
        //采用中序遍历，二叉搜索树的中序序列是递增序列
        if(root==nullptr){
            return;
        }
        dfs(root->left);
        update(root->val);
        dfs(root->right);
    }
    vector<int> findMode(TreeNode* root) {
        dfs(root);
        return answer;
    }
};

? ? ? ? 2.前驱指针

?

class Solution {
public:
    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 { // 与前一个节点数值不同
            count = 1;
        }
        pre = cur; // 更新上一个节点

        if (count == maxCount) { // 如果和最大值相同，放进result中
            result.push_back(cur->val);
        }

        if (count > maxCount) { // 如果计数大于最大值频率
            maxCount = count;   // 更新最大频率
            result.clear();     // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
            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. 二叉树的最近公共祖先?

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树:? root =?[3,5,1,6,2,0,8,null,null,7,4]

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;
        }
    }
};

?

?

?