Tree Find Mode in Binary Search

思路1 利用map存储对应的节点，

/**
 * 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 先了解几个特性
1 二叉搜索树左（右）子树的值小于等于（大于等于）节点的值的特性
2 从1可以推导出某一节点的右子树的所有节点的值大于或等于左子树的节点的值。
3 假设出现下图的情形，可以根据1 2 推断出
node0->val <= node1->val <=father->val <= grand->val
利用3可以在不使用map的情况下设计一递归的算法 计算出问题的答案。

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 思路抽象来说是将树变为“线性的树”（描述可能不太准确），然后取“”线性树”上的值进行比较。具体描述请看下图:

有一点需要主要的是没访问一个节点的时候根节点的时候，需要判断前一节点是否和当前访问节点的左子树(如果有的话)的节点是否相同，若相同的话(例如图中节点10)要直接访问右节点而不再去访问左节点，不然的话会出现无限循环的情况。

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