diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /find_mode_bst.py | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'find_mode_bst.py')
-rw-r--r-- | find_mode_bst.py | 44 |
1 files changed, 44 insertions, 0 deletions
diff --git a/find_mode_bst.py b/find_mode_bst.py new file mode 100644 index 0000000..b53ed61 --- /dev/null +++ b/find_mode_bst.py @@ -0,0 +1,44 @@ +# 501. Find Mode in Binary Search Tree + +""" +given the 'root' of a binary search tree with duplicates, return all the +'modes(s)' (ie. the most frequently occured element in it). if the tree has +more than one mode, return them in any order. +""" + + +class TreeNode(object): + def __init__(self, val=0, left=None, right=None): + self.val = val + self.left = left + self.right = right + + +class Solution(object): + prev = None + max_cnt = 0 + curr_cnt = 0 + ans = [] + + def dfs(self, node): + if not node: + return + self.dfs(node.left) + self.curr_cnt = 1 if node.val != self.prev else self.curr_cnt + 1 + if self.curr_cnt == self.max_cnt: + self.ans.append(node.val) + elif self.curr_cnt > self.max_cnt: + self.ans = [node.val] + self.max_cnt = self.curr_cnt + self.prev = node.val + self.dfs(node.right) + + def findMode(self, root): + self.dfs(root) + return self.ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.findMode([1, None, 2, 2])) # expect: 2 + print(obj.findMode([0])) # expect: 0 |