FXTi's blog
0%

find-mode-in-binary-search-tree

Posted on Edited on

Find Mode in Binary Search Tree – LeetCode 501

Problem

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.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 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<int> findMode(TreeNode* root) {
		vector<int> res;
		int mx = 0, cnt = 1;
		inorder(root,pre,cnt,mx,res);
		return res;
	}

	void inorder(TreeNode* node, TreeNode* &pre,int &cnt, int &mx, vector<int> &res){
		if(!node) return;
		inorder(node->left, pre,cnt, mx, res);
		if(pre)
			cnt = (node->val == pre->val)? cnt + 1: 1;
		if(cnt >= mx){
			if(cnt > mx) res.clear();
			res.push_back(node->val);
			mx = cnt;
		}
		pre = node;
		inorder(node->right, pre,cnt, mx, res);
	}
};

思路

使用中序遍历来提供对原有大小顺序的保存，于是可以在One Pass情况下统计出现次数。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$14$ ms，排名$0.57\%$

Better

思路

还没看到更好的思路。