aboutsummaryrefslogtreecommitdiff
path: root/find_mode_bst.py
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /find_mode_bst.py
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'find_mode_bst.py')
-rw-r--r--find_mode_bst.py44
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