Java实现 LeetCode 501 二叉搜索树中的众数

我就是我 2023-07-17 14:05 13阅读 0赞

## 501. 二叉搜索树中的众数 ##

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值  
结点右子树中所含结点的值大于等于当前结点的值  
左子树和右子树都是二叉搜索树  
例如：  
给定 BST \[1,null,2,2\],

1
        \
         2
        /
       2

返回\[2\].

提示：如果众数超过1个，不需考虑输出顺序

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

PS：  
遍历

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
          int preVal = 0, curTimes = 0, maxTimes = 0;
        ArrayList<Integer> list = new ArrayList<Integer>();
        public int[] findMode(TreeNode root) { 
    	traversal(root); 
    	int size = list.size();
    	int[] ans = new int[size];
    	for(int i = 0; i < size; i++){ 
    	    ans[i] = list.get(i);
    	}
    	return ans;
        }
        //二叉搜索树中序遍历是递增顺序
        public void traversal(TreeNode root){ 
    	if(root != null){ 
    	    traversal(root.left);
    	    //判断当前值与上一个值的关系, 更新 curTimes 和 preVal
    	    if(preVal == root.val){ 
    		curTimes++;
    	    }else{ 
    		preVal = root.val;
    		curTimes = 1;
    	    }
    	    //判断当前数量与最大数量的关系, 更新 list 和 maxTimes
    	    if(curTimes == maxTimes){ 
    		list.add(root.val);
    	    }else if(curTimes > maxTimes){ 
    		list.clear();
    		list.add(root.val);
    		maxTimes = curTimes;
    	    }
    	    traversal(root.right);
    	}
        }
    }