[leetcode] 501. Find Mode in Binary Search Tree

[leetcode] 501. Find Mode in Binary Search Tree

Description

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],

1 \ 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).

分析

题目的意思是：找出二叉查找树中的众数。

其中一种方法是中序遍历，然后map计算词频，然后再遍历一次，然后求出结果。这里是另一种方法，中序遍历是有序的，所以只要跟前一个节点比较，如果相等，则cnt+1，不等，置1，并且重新进行统计。

代码

/** * 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 findMode(TreeNode* root) { vector res; int mx=0,cnt=1; TreeNode* pre=NULL; solve(root,pre,cnt,mx,res); return res; } void solve(TreeNode* root,TreeNode* &pre,int& cnt,int& mx,vector& res){ if(!root){ return ; } solve(root->left,pre,cnt,mx,res); if(pre){ cnt= root->val==pre->val ? cnt+1:1; } if(cnt>mx){ res.clear(); res.push_back(root->val); mx=cnt; }else if(cnt==mx){ res.push_back(root->val); } pre=root; solve(root->right,pre,cnt,mx,res); }};

参考文献

​​[LeetCode] Find Mode in Binary Search Tree 找二分搜索数的众数​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。