[LeetCode] 501. Find Mode in Binary Search Tree

NikoManiac 发布于2019-08-16 13:51 / 763人阅读

Problem

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node"s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node"s key.
Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

Solution

class Solution {
    int count = 0;
    int maxCount = 0;
    Integer pre = null;
    public int[] findMode(TreeNode root) {
        List resList = new ArrayList<>();
        helper(root, resList);
        return resList.stream().mapToInt(i->i).toArray();
    }
    private void helper(TreeNode root, List res) {
        if (root == null) return;
        helper(root.left, res);
        if (pre == null) {
            pre = root.val;
            count = 1;
            maxCount = 1;
            res.add(root.val);
        } else {
            if (root.val == pre) {
                count++;
                if (count > maxCount) {
                    res.clear();
                    maxCount = count;
                }
            } else {
                pre = root.val;
                count = 1;
            }
            if (count == maxCount) {
                res.add(root.val);
            }
        }
        helper(root.right, res);
    }
}

云服务器 GPU云服务器 binary-search-tree binary-tree binary-search FIND_IN_SET

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72459.html

前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
[Leetcode] Closest Binary Search Tree Value 最近二叉搜索

摘要：递归法复杂度时间空间思路根据二叉树的性质，我们知道当遍历到某个根节点时，最近的那个节点要么是在子树里面，要么就是根节点本身。因为我们知道离目标数最接近的数肯定在二叉搜索的路径上。 Closest Binary Search Tree Value I Given a non-empty binary search tree and a target value, find the va...

AlphaWallet 2019-08-14 12:37 评论0 收藏0
LeetCode[270] Closest Binary Search Tree Value

摘要：复杂度思路用一个变量来记录当前的值，并且在每次之前，比较得到目前的最大值。注意变量的比较不要用代码 LeetCode[270] Closest Binary Search Tree Value Given a non-empty binary search tree and a target value, find the value in the BST that is close...

pumpkin9 2019-08-14 15:02 评论0 收藏0
[LeetCode] 270. Closest Binary Search Tree Value

Problem Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target. Note: Given target value is a floating point.You are guaranteed to have only o...

XUI 2019-08-16 13:49 评论0 收藏0
[Leetcode] Lowest Common Ancestor of a Binary Tree

摘要：如果子树中有目标节点，标记为那个目标节点，如果没有，标记为。显然，如果左子树右子树都有标记，说明就已经找到最小公共祖先了。如果在根节点为的左右子树中找的公共祖先，则必定是本身。只有一个节点正好左子树有，右子树也有的时候，才是最小公共祖先。 Lowest Common Ancestor of a Binary Search Tree 最新更新请见：https://yanjia.me/zh...

Dr_Noooo 2019-08-14 12:25 评论0 收藏0