leetcode 501. Find Mode in Binary Search Tree

2019-11-08 00:41:00

字体：大中小

来源：转载

供稿：网友

头文件说明：该头文件为一些简单是二叉树操作，提交leetcode时不需要，只是为了本地测试而已~

#ifndef _TREE_INCLUDE_H_ #define _TREE_INCLUDE_H_#include <iostream>#include <vector>#include <algorithm>#include <string>using namespace std;// 节点数据结构struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};//使用数组创建二叉树void CreateNode(const vector<int>& v, TreeNode* cur, int curIndex){ int len = v.size(); if (len == 0 || cur == NULL || curIndex < 0 || curIndex >= len) return; if ((2 * curIndex + 1 < len) && (v[2*curIndex+1] != -1)) { TreeNode* tmp = new TreeNode(v[2 * curIndex + 1]); cur->left = tmp; } else cur->left = NULL; if ((2 * curIndex + 2 < len) && (v[2*curIndex+2] != -1)) { TreeNode* tmp = new TreeNode(v[2 * curIndex + 2]); cur->right = tmp; } else cur->right = NULL; CreateNode(v, cur->left, 2 * curIndex + 1); CreateNode(v, cur->right, 2 * curIndex + 2);}TreeNode* CreateTree(const vector<int>& v){ int len = v.size(); if (len == 0) return NULL; TreeNode* root = new TreeNode(v[0]); CreateNode(v, root, 0); return root;}void FirstOrderTraverse(TreeNode* root){ if (root == NULL) return; cout << root->val << " "; FirstOrderTraverse(root->left); FirstOrderTraverse(root->right); //cout << endl;}void MakeEmpty(TreeNode* root){ if (root != NULL) { MakeEmpty(root->left); MakeEmpty(root->right); delete root; }}#endif // /*leetcode 501. Find Mode in Binary Search TreeGiven a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.题目大意：对于BST树，给出出现次数最多的元素解题思路：1. 遍历一遍，用map记录元素和出现的次数，并记录出现的做多次数，然后遍历map2. 中序遍历并递归*/#include <iostream>#include <vector>#include <algorithm>#include <map>#include "TreeInclude.h"using namespace std;class Solution1 {public: vector<int> findMode(TreeNode* root) { vector<int> ret; if (root == NULL) return ret; map<int, int> mmap; int maxCount = 0; Traverse(root, mmap, maxCount); for (auto iter = mmap.begin(); iter != mmap.end(); ++iter) { if (iter->second == maxCount) ret.push_back(iter->first); } return ret; } void Traverse(TreeNode* root, map<int, int>& mmap, int& maxCount) { if (root == NULL) return; int count = ++mmap[root->val]; maxCount = max(maxCount, count); Traverse(root->left, mmap, maxCount); Traverse(root->right, mmap, maxCount); }};class Solution{public: vector<int> findMode(TreeNode* root) { vector<int> ret; //return reslut; if (root == NULL) return ret; int curVal=0x7fffffff, MaxCnt = 0, curCnt = 0; //Inorder(root, ret) Inorder(root, ret, curVal, MaxCnt, curCnt); return ret; } /* 参数说明： root-根节点 ret-保存的出现次数最多的 curVal-当前遍历的值 MaxCnt-最多出现的次数 curCnt-当前出现的次数记录当前元素和其出现的次数。如果root->val等于当前元素值，curCnt+1,不等，则是第一次出现如果当前元素出现次数curCnt>MaxCnt,那么清空ret,并将curVal压入，如果等于，则直接压入curVal */ void Inorder(TreeNode* root, vector<int>& ret, int& curVal, int& MaxCnt, int& curCnt) { if (root == NULL) return; Inorder(root->left, ret, curVal, MaxCnt, curCnt); if (root->val == curVal) ++curCnt; else { curCnt = 1; curVal = root->val; } if (curCnt > MaxCnt) { ret.clear(); ret.push_back(curVal); MaxCnt = curCnt; } else if (curCnt == MaxCnt) { ret.push_back(curVal); } Inorder(root->right, ret, curVal, MaxCnt, curCnt); }};void TEST(){ vector<int> v{ 1,-1,2,-1,-1, 2 }; TreeNode* root = CreateTree(v); //FirstOrderTraverse(root); //cout << endl; Solution sol; vector<int> ret = sol.findMode(root); for (auto v : ret) cout << v << " "; cout << endl;} int main(){ TEST(); return 0;}

上一篇：EntityManager 详解

下一篇：session和cookie的区别