LeetCode_二叉树_简单_501.二叉搜索树中的众数

x33g5p2x  于2022-03-31 转载在 其他  
字(1.6k)|赞(0)|评价(0)|浏览(333)

1.题目

给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有众数(即,出现频率最高的元素)
如果树中有不止一个众数,可以按任意顺序返回。

假定 BST 满足如下定义:
结点左子树中所含节点的值小于等于当前节点的值
结点右子树中所含节点的值大于等于当前节点的值
左子树和右子树都是二叉搜索树

示例 1:

输入:root = [1,null,2,2]
输出:[2]

示例 2:
输入:root = [0]
输出:[0]

提示:
树中节点的数目在范围 [1, 104] 内
-105 <= Node.val <= 105

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-mode-in-binary-search-tree

2.思路

(1)中序遍历

3.代码实现(Java)

//思路1————中序遍历
/**
 * 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 {

    //res用于保存最终结果,返回时将其转换为数组即可
    ArrayList<Integer> res = new ArrayList<>();
    //preNode表示通过中序遍历到的当前节点的前驱节点
    TreeNode preNode = null;
    //当前元素的重复次数
    int curCnt = 0;
    //全局最长相同序列长度
    int maxCnt = 0;
    
    public int[] findMode(TreeNode root) {
        traverse(root);
        /*
            ArrayList<Integer>如何转化为int[]数组?
            Java8新特性:想要转换成int[]类型,就得先转成IntStream
            这里可以通过mapToInt()把Stream<Integer>调用Integer::valueOf来转成IntStream
            然后再用IntStream中默认的toArray()转成int[]
        */
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }
    
    //中序遍历二叉搜索树
    public void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        //遍历当前根节点的左子树
        traverse(root.left);
        
        //此时可将root节点看成当前遍历到的节点
        if (preNode == null) {
            //初始化前驱节点
            res.add(root.val);
            curCnt = 1;
            maxCnt = 1;
        } else {
            if (root.val == preNode.val) {
                //当前节点的值与前驱节点的值相同
                curCnt++;
                if (curCnt == maxCnt) {
                    //当前节点的值为众数
                    res.add(root.val);
                } else if (curCnt > maxCnt) {
                    //更新众数
                    maxCnt = curCnt;
                    res.clear();
                    res.add(root.val);
                }
            } else {
                //当前节点的值与前驱节点的值不同
                curCnt = 1;
                if (curCnt == maxCnt) {
                    res.add(root.val);
                }
            }
        }
        //更新前驱节点
        preNode = root;
        
        //遍历当前根节点的右子树
        traverse(root.right);
    }
}

相关文章