501. Find Mode in Binary Search Tree
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:
? For example: 1 2 / 2 ? return? 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). 思路: 对于本题中的二叉搜索树,节点的排列是有顺序的,左节点<=当前节点<=右节点。也就是说,假设这样一种情况:存在大于等于3个的连续相同的节点,且当前节点存在左右子树,那么相同的三个节点一定是:当前节点、左子树中最大的节点和右子树中最小的节点。 这里我们容易想到的是中序遍历(对于整个树,先遍历左节点,再遍历中间节点,最后遍历右节点),使用中序遍历遍历二叉搜索树,可以获得一个从小到大的排好序的升序序列。 所以分析到这里,题目就转化成:给定一个升序序列,寻找重复次数最多的数字 , 所以 /** * 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) { tmp_cnt = 0; max_cnt = 0; cur_value = 0; inorder(root); return result; } private: int tmp_cnt; int max_cnt; int cur_value; vector<int> result; void inorder(TreeNode* root){ if (root == NULL){ return; } // 遍历左子树 inorder(root->left); tmp_cnt++; if (cur_value != root-> val){ cur_value = root-> val; tmp_cnt = 1; } if (tmp_cnt > max_cnt){ max_cnt = tmp_cnt; result.clear(); result.push_back(root->val); }else if (tmp_cnt == max_cnt){ result.push_back(root->val); } // 遍历右子树 inorder(root->right); } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |