思路1 利用map存儲(chǔ)對(duì)應(yīng)的節(jié)點(diǎn)，

/**
 * 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 {
    
unordered_map<int,int> m; 
int max = 0;
vector<int> vecResult;
public:
    vector<int> findMode(TreeNode* root) {

        return  getMap(root);

    }
    
    vector<int> getMap(TreeNode* root){
        if(!root){
            return vecResult;
        }
        
        int val = ++m[root->val];  
       if(max == 0){
          max = val;
          vecResult.push_back(root->val);
        }else if(val > max){
          max = val;   
          vecResult.erase(vecResult.begin(), vecResult.end());
          vecResult.push_back(root->val);
        }else if(val == max){
          vecResult.push_back(root->val);
        }
        
        getMap(root->left);
        getMap(root->right);
        return vecResult;
    }
};

算法2 先了解幾個(gè)特性
1 二叉搜索樹左（右）子樹的值小于等于（大于等于）節(jié)點(diǎn)的值的特性
2 從1可以推導(dǎo)出某一節(jié)點(diǎn)的右子樹的所有節(jié)點(diǎn)的值大于或等于左子樹的節(jié)點(diǎn)的值。
3 假設(shè)出現(xiàn)下圖的情形，可以根據(jù)1 2 推斷出
node0->val <= node1->val <=father->val <= grand->val
利用3可以在不使用map的情況下設(shè)計(jì)一遞歸的算法 計(jì)算出問題的答案。

tree0.png

class Solution {
    // **ans** contains the result.
    vector<int> ans;
   // **cur** variable is the cur occurrence, **occ** variable is the max occurrence.
    int cur = 0, occ = 0;
    // **pre** variable is the previous node address, we do inorder travel.
    TreeNode* pre = NULL;
    void inorder(TreeNode* root) {
        
        if(!root){
           return;
        } 
        inorder(root->left);
        
        // this step give of the occurrence  of root->val.
        if(!pre || pre->val != root->val){
            cur = 1;
        }else{ 
            cur++;
        }
        
        //if cur == occ, we just add root->val to our ans, if(cur > occ), 
        //ans = {root->val}.

        if(cur >= occ) {
            if(cur > occ) {
                ans = {};
                occ = cur;
            }
            ans.push_back(root->val);
        }
        pre = root;
        inorder(root->right);//
    }
    
public:
    vector<int> findMode(TreeNode* root) {
        inorder(root);
        return ans;
    }
};

算法3 思路抽象來說是將樹變?yōu)椤熬€性的樹”（描述可能不太準(zhǔn)確），然后取“”線性樹”上的值進(jìn)行比較。具體描述請(qǐng)看下圖:

有一點(diǎn)需要主要的是沒訪問一個(gè)節(jié)點(diǎn)的時(shí)候根節(jié)點(diǎn)的時(shí)候，需要判斷前一節(jié)點(diǎn)是否和當(dāng)前訪問節(jié)點(diǎn)的左子樹(如果有的話)的節(jié)點(diǎn)是否相同，若相同的話(例如圖中節(jié)點(diǎn)10)要直接訪問右節(jié)點(diǎn)而不再去訪問左節(jié)點(diǎn)，不然的話會(huì)出現(xiàn)無限循環(huán)的情況。

vector<int> findMode(TreeNode* root) {
    vector<int> modes;
    
    int count = 0;
    int countMax = 0;
    bool hasVisited = false;
    int preVal;

    TreeNode* cur = root;
    TreeNode* pre = NULL;
    while (cur) {
        if (cur->left) {
            pre = cur->left;
            while (pre->right && pre->right != cur) {
                pre = pre->right;
            }

            if (pre->right) {
                pre->right = NULL;
                if (hasVisited) {
                    if (preVal == cur->val) {
                        ++count;
                    }
                    else {
                        preVal = cur->val;
                        count = 1;
                    }
                    if (countMax < count) {
                        countMax = count;
                        modes.clear();
                        modes.push_back(cur->val);
                    }
                    else if (countMax == count) {
                        modes.push_back(cur->val);
                    }
                }
                else {
                    count = countMax = 1;
                    preVal = cur->val;
                    modes.push_back(cur->val);
                    hasVisited = true;
                }
                cur = cur->right;
            }
            else {
                pre->right = cur;
                cur = cur->left;
            }
        }
        else {
            if (hasVisited) {
                if (preVal == cur->val) {
                    ++count;
                }
                else {
                    preVal = cur->val;
                    count = 1;
                }

                if (countMax < count) {
                    countMax = count;
                    modes.clear();
                    modes.push_back(cur->val);
                }
                else if (countMax == count) {
                    modes.push_back(cur->val);
                }
            }
            else {
                count = countMax = 1;
                preVal = cur->val;
                modes.push_back(cur->val);
                hasVisited = true;
            }
            cur = cur->right;
        }    
    }
    return modes;
}