Shulou(Shulou.com)06/01 Report--

This article introduces the knowledge about "Python how to find all modes in the binary search tree". In the actual case operation process, many people will encounter such difficulties. Next, let Xiaobian lead you to learn how to deal with these situations! I hope you can read carefully and learn something!

Topic: Find all modes (most frequent elements) in the binary search tree.

Idea: the binary search tree defined here is a node of the left subtree of all nodes are less than or equal to the value of the node, the right subtree is the opposite, greater than or equal to. At the same time, follow up says let's not use extra space beyond the implicit stack in recursion, so we can't use hash tables. Because it is a binary search tree, then the results we traverse in order are ordered, we only need to compare whether the two elements before and after are equal, we can count the number of times an element appears, because the same element can be determined to be all together. We need a node variable pre to record the last node traversed, mx to record the maximum number of times, and cnt to count the number of times the current element appears. When traversing in order, if pre is not empty, it means that the current node is not the first node. We compare it with the previous node. If it is equal, cnt increments by 1. If it is not equal, cnt resets by 1. If cnt is greater than mx, then we empty the result res and add the current node value to the result res. If cnt is equal to mx, then we add the current node value to the result res and assign mx to cnt. Finally, we update pre to the current node. If pre is empty, the current node is the root node. Then we create a new node and assign it the current node value.

Language : cpp

/** * 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) {if (! root) return {};vector res; TreeNode *now = root, *pre = NULL;stack s;int mx = 0, cnt = 1;while (! s.empty() || now) {while (now) { //middle order traversal, left middle right. push(now) the left subtree of each node; now = now->left; } now = s.top (); s.pop(); //fetch top element if (pre) { //Determine whether the current element and the previous element have the same value, the same cnt count plus one cnt = (now->val = pre->val) ? cnt + 1 : 1; } //If cnt is greater than or equal to mx, it means that the number of repetitions of the current element is greater than the number of repetitions of the previous largest element, and the new result needs to be put into the result stack. if (cnt >= mx) {if (cnt > mx) res.clear(); res.push_back(now->val); mx = cnt; }if (! pre) pre = new TreeNode(now->val); pre->val = now->val; now = now->right; }return res; }};

Language : python

# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object):def findMode(self, root):""" :type root: TreeNode :rtype: List[int] """res = [] s = [] now = root pre = Nonemx, cnt = 0, 1while s or now:while now: s.append(now) now = now.left now = s.pop(len(s) - 1)if pre:if now.val == pre.val: cnt = cnt + 1else: cnt = 1if cnt >= mx:if cnt > mx:del res[:] res.append(now.val) mx = cntif not pre: pre = TreeNode(now.val) pre.val = now.val now = now.rightreturn res"Python how to find all the modes in the binary search tree" content introduced here, thank you for reading. If you want to know more about industry-related knowledge, you can pay attention to the website. Xiaobian will output more high-quality practical articles for everyone!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.