【LeetCode 42】501.二叉搜尋樹中的衆數

文章目錄

• ​​【LeetCode 42】501.二叉搜尋樹中的衆數​​
• ​​一、題意​​
• ​​二、解答過程​​

一、題意

二、解答過程

在 《二叉樹：搜尋樹的最小絕對值差》​中我們用到了 ​

​pre​

​​指針和 ​

​cur​

​指針的技巧。這裡又用上了。

弄一個指針指向前一個節點，這樣每次cur（目前節點）才能和pre（前一個節點）作比較。

而且初始化時pre==NULL,這樣當pre為NULL時，我們就知道這是比較的第一個元素。

if (pre == NULL) { // 第一個節點
    count = 1; // 頻率為1
} else if (pre->val == cur->val) { // 與前一個節點數值相同
    count++;
} else { // 與前一個節點數值不同
    count = 1;
}
pre = cur; // 更新上一個節點      

如何周遊一遍就能找到所有衆數呢？

if (count > maxCount) { // 如果計數大于最大值
    maxCount = count;   // 更新最大頻率
    result.clear();     // 很關鍵的一步，不要忘記清空result，之前result裡的元素都失效了
    result.push_back(cur->val);
}      

class Solution {
public:
    int maxCount;//最大頻率
    int count;//統計頻率
    TreeNode* pre;
    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;
    }

    vector<int> findMode(TreeNode* root) {
        count=0;
        maxCount=0;
        TreeNode* pre=NULL;//記錄前一個節點
        result.clear();

        searchBST(root);
        return result;

    }
};