501. 二叉搜索树中的众数

中序递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode pre ;
    int count ; //统计频率
    int maxCount; //最大频率
    List<Integer> resL = new ArrayList<>();
    public int[] findMode(TreeNode root) {
        count = 0;
        maxCount = 0;
        pre = null;
        resL.clear();
        searchBST(root);
        int size = resL.size();
        int [] res = new int[ size];
        for(int i = 0 ; i < size; i++ ) {
            res[i] = resL.get(i);
        }
        return res;
    }
    public 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 ) { // 如果和最大值相同，放进resL中
            resL.add(cur.val);
        }
        if(count > maxCount ) {
            resL.clear();   // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
            resL.add(cur.val);
            maxCount = count;  // 更新最大频率
        }
        searchBST(cur.right);
        return ;
    }
}

迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int[] findMode(TreeNode root) {
        if(root == null ) return new int[0];
        //迭代 中序
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        TreeNode cur = root;
        int cnt = 0;
        int maxCnt = 0;
        List<Integer> list = new ArrayList<>();
        while( cur != null || !stack.isEmpty() ) { 
            if(cur != null ) { //左
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                if(pre == null ) {
                    cnt = 1;
                } else if(pre.val == cur.val ) {
                    cnt++;
                } else {
                    cnt = 1;
                }
                if(cnt == maxCnt ) {
                    list.add(cur.val);
                } else if(cnt > maxCnt ) {
                    list.clear();
                    maxCnt = cnt;
                    list.add(cur.val);
                }
                 pre = cur;
                 cur = cur.right;  //右
            }
        }
        int size = list.size();
        int[] res = new int[size];
        for(int i = 0; i < size; i++ ) {
            res[i] = list.get(i);
        }
        return res;
    }
}