Leetcode501. 二叉搜索树中的众数(二叉树)

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：
结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],

1

2
/
2
返回[2].
提示：如果众数超过1个，不需考虑输出顺序
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

/*
思路：
先遍历二叉树，找出所有val到record数组中
从record数组中找出最大重复数字的位数
遍历record数组，找出众数
注意点：
    pos为全局变量，在leetcode提交过程中，因为会重复调用，pos每次用完后需要置0,
*/
void quick_sort(int *arr, int start, int end){
	if (start >= end) return;
	int i = start;
	int j = end;
	while (i < j)
	{
		while (arr[j] >= arr[start] && i < j) // 从基准数的对面开始走
	        j--;
		while (arr[i] <= arr[start] && i < j)
            i++;
		if (i < j){
			int tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
		}
	}
	int tmp = arr[start];
	arr[start] = arr[i];
	arr[i] = tmp;

	quick_sort(arr, start, i -1);
	quick_sort(arr, i + 1, end);
}

int count_num(struct TreeNode* root){
    return  !root ? 0 : 1 + count_num(root->left) + count_num(root->right);
}

int pos = 0;
void do_process(struct TreeNode* root, int *record){
    if(!root) return;
    record[pos] = root->val;
    pos++;  
    do_process(root->left, record);
    do_process(root->right, record);
    return;
}

int* findMode(struct TreeNode* root, int* returnSize){
    int count = count_num(root);
    int *record = (int *)calloc(1, count * sizeof(int));
    do_process(root, record);
    quick_sort(record, 0, count - 1);
    pos = 0; // leetcode多个案例，此处需要置0
    int i = 0;
    int max = 1;
    int rnum = 1;
    for(; i < count - 1; i++){
        if(record[i] == record[i + 1]) rnum++;
        else rnum = 1;
        if(rnum > max) max = rnum;
    }
    if(1 == max){
        *returnSize = count;
        return record;
    }

    int *ret = (int *)malloc(count * sizeof(int));
    int j = 0;
    for(i = 0; i <= count - max;){
        if(record[i] == record[i + max - 1]){
            ret[j++] = record[i];
            i += max;
        }else i++;

    }
    
    *returnSize = j;
    return ret;
}