【树】501. 二叉搜索树中的众数

题目:

【树】501. 二叉搜索树中的众数

 

 

解决:

通过大佬题解 了解二叉搜索树的一个重要特性是中序遍历递增,那么根据这个特性可以很容易的得到一个递增的数组,然后对该数组进行判断即可得出结果。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<int> vec;
13     vector<int> result;
14     int max = 0;
15     int cur = 0;
16     vector<int> findMode(TreeNode* root) 
17     {
18         inOrder(root);
19 
20         if(vec.size()==1)
21         {
22             result.push_back(vec[0]);
23         }
24 
25         for(int i=1; i<vec.size(); i++)
26         {
27             if(vec[i]==vec[i-1])
28             {
29                 cur++;
30             }
31             else
32             {
33                 cur = 0;
34             }
35 
36             if(cur == max)
37             {
38                 if(i==1 && cur ==0)
39                 {
40                     result.push_back(vec[0]);
41                 }
42                 result.push_back(vec[i]);
43             }
44             else if(cur >max)
45             {
46                 result.clear();
47                 max = cur;
48                 result.push_back(vec[i]);
49             }
50         }
51 
52         return result;
53     };
54 
55     void inOrder(TreeNode* root)
56     {
57         if(!root)
58         {
59             return;
60         }
61         inOrder(root->left);
62         vec.push_back(root->val);
63         inOrder(root->right);
64     }
65 };

 

上一篇:面试题07. 根据前序和中序重建二叉树


下一篇:《剑指Offer(第二版)》面试题07. 重建二叉树