lc501.二叉搜索树中的众数【线索二叉树Morris遍历-＞lc538】_lc538a

开始想的按普通二叉树一样，把值和计数放在一个数组里面，但是想想它是二叉搜索树，有什么特别的呢？

官方题解https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/solution/er-cha-sou-suo-shu-zhong-de-zhong-shu-by-leetcode-/ 

1）先中序遍历得到顺序数组，然后遍历数组并计数。

2）*****Morris遍历（中序），使用跟lc538反序中序遍历一样的方法，一边建立线索，一边中序遍历，一边计数

【注意点】1.最开始写的fun(node->val,num)，num是值传递，就没有更新num的值，结果就错了；2.最开始忘记了&&pre->right!=node。记得如果是第二次找前驱，最终不会遇到NULL，而会遇到node自己。

/**
 * 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> re;
    int maxcount=0,count=0,num=0;
 
    vector<int> findMode(TreeNode* root) {
        TreeNode* node=root;
        while(node){
            if(!node->left){  //无左子树，访问node，去往node->right
                fun(node->val);  //最开始写的fun(node->val,num)，num是值传递，就没有更新num的值，结果就错了
                node=node->right;
            }else{  //左子树存在，找前驱
                TreeNode* pre=FindPre(node);
                if(!pre->right){  //如果没有线索，建立线索，然后node继续遍历
                    pre->right=node;
                    node=node->left;
                }else{  //如果已经建立线索，则访问node，去往node->right
                    pre->right=NULL;
                    fun(node->val);
                    node=node->right;
                }
            }
        }
        return re;
    }
 
    void fun(int val){
        if(val==num){  //结点值不变
            count++;
        }else{  //结点值改变
            count=1;  //重新计数
            num=val;
        }
        if(count>maxcount){  //计数变大
            maxcount=count;  //更新maxcount
            re=vector<int> {num};
        }else if(count==maxcount){  //计数同最大，val加入re
            re.push_back(val);
        }//计数未达到最大，直接重新计数
    }
 
    TreeNode* FindPre(TreeNode* node){
        TreeNode* pre=node->left;
        while(pre->right&&pre->right!=node)  //最开始忘记了&&pre->right!=node。记得如果是第二次找前驱，最终不会遇到NULL，而会遇到node自己
            pre=pre->right;
        return pre;
    }
};