Python怎么找到二叉搜索樹中的所有mode

本篇內(nèi)容介紹了“Python怎么找到二叉搜索樹中的所有mode”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細閱讀，能夠?qū)W有所成！

成都創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比霞浦網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式霞浦網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋霞浦地區(qū)。費用合理售后完善，10多年實體公司更值得信賴。

題目：找到二叉搜索樹中的所有mode(出現(xiàn)最頻繁的元素)。

思路：這里定義的二叉搜索樹的一個結(jié)點的左子樹中所有結(jié)點的值都小于或等于該結(jié)點的值，右子樹則相反，大于或等于。于此同時，follow up說讓我們不用除了遞歸中的隱含棧之外的額外空間，因此不能使用哈希表。由于是二叉搜索樹，那么我們中序遍歷出來的結(jié)果就是有序的，我們只需要比較前后兩個元素是否相等，就能統(tǒng)計某個元素出現(xiàn)的次數(shù)，因為相同的元素可定是都在一起的。我們需要一個結(jié)點變量pre來記錄上一個遍歷到的結(jié)點，然后mx記錄最大的次數(shù)，cnt計數(shù)當(dāng)前元素出現(xiàn)的次數(shù)。中序遍歷的時候，如果pre不為空，說明當(dāng)前不是第一個結(jié)點，我們和之前一個結(jié)點比較，如果相等，則cnt自增1，如果不等，cnt重置1。如果此時cnt大于mx，那么我們清空結(jié)果res，并把當(dāng)前結(jié)點值放入結(jié)果res，如果cnt等于mx，那么我們直接將當(dāng)前結(jié)點值加入結(jié)果res，然后mx賦值為cnt。最后我們把pre更新為當(dāng)前結(jié)點。如果pre為空，說明當(dāng)前結(jié)點是根結(jié)點。那么我們新建一個結(jié)點并賦上當(dāng)前結(jié)點值。

Language : cpp

/**
 * 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) {if (!root) return {};vector<int> res;
        TreeNode *now = root, *pre = NULL;stack<TreeNode*> s;int mx = 0, cnt = 1;while (!s.empty() || now) {while (now) {             //中序遍歷，左中右。將每個結(jié)點的左子樹入棧s.push(now);
                now = now->left;
            }
            now = s.top(); s.pop(); //取棧頂元素if (pre) {              //判斷當(dāng)前元素和上一個元素值是否一樣，一樣cnt計數(shù)加一cnt = (now->val == pre->val) ? cnt + 1 : 1;
            }                       //如果cnt大于等于mx，說明當(dāng)前元素重復(fù)次數(shù)大于之前最大的重復(fù)元素的次數(shù)，需要將新結(jié)果入結(jié)果棧。if (cnt >= mx) {if (cnt > mx) res.clear();
                res.push_back(now->val);
                mx = cnt;
            }if (!pre) pre = new TreeNode(now->val);
            pre->val = now->val;
            now = now->right;
        }return res;
    }
};

Language : python

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):def findMode(self, root):"""
        :type root: TreeNode
        :rtype: List[int]
        """res = []
        s = []
        now = root
        pre = Nonemx, cnt = 0, 1while s or now:while now:
                s.append(now)
                now = now.left
            now = s.pop(len(s) - 1)if pre:if now.val == pre.val:
                    cnt = cnt + 1else:
                    cnt = 1if cnt >= mx:if cnt > mx:del res[:]
                res.append(now.val)
                mx = cntif not pre:
                pre = TreeNode(now.val)
            pre.val = now.val
            now = now.rightreturn res

“Python怎么找到二叉搜索樹中的所有mode”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！

文章題目：Python怎么找到二叉搜索樹中的所有mode
地址分享：http://bm7419.com/article6/igceog.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供服務(wù)器托管、品牌網(wǎng)站建設(shè)、商城網(wǎng)站、自適應(yīng)網(wǎng)站、移動網(wǎng)站建設(shè)、手機網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)