Finding Most Frequent Duplicates Mode(s) in Binary Search Tree (BST) in C

描述

不同於傳統二元搜尋樹，節點的值可以重複，所以左子樹的值小於等於根的值，右子樹的值大於等於根的值，在樹上找到重複頻率最高的節點(們)並回傳

範例

輸入：空樹
輸出：{}

輸入：單節點

    0
   / \

輸出：{0}

輸入：不同節點各出現一次

    0
     \
      1

輸出：{0,1}

輸入：某節點出現二次

    1
     \
     (2)
     /
   (2)

輸出：{2}

輸入：某些節點出現二次

    (3)
   /   \
 (1)    5
 / \   / \
0   2 4   6
   / \
 (1) (3)

輸出：{1,3}

想法

要先知道哪些/個節點出現頻率最高，必須先走訪節點們比一次。取得最高頻率後，找出節點出現頻率等於最高頻率的個數，用這個動態分配回傳陣列的記憶體，再走訪一次把出現頻率最高的節點(們)加入陣列。

情境是記憶體有限，想一次走訪用雜湊表紀錄節點值和頻率，除了發生衝突(conflict)會算錯頻率，記憶體因為表太大爆掉，變成不得不用時間換空間。

實作

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

void get_modes(struct TreeNode *root, double *last, int *freq, int max, int *modes, int *i)
{
    int val = root->val;
    
    if (root->left)
        get_modes(root->left, last, freq, max, modes, i);

    if (*last != val)
    {
        *freq = 1;
        *last = val;
    }
    else
        (*freq)++;
    
    if (*freq == max)
    {
        modes[*i] = *last;
        (*i)++;
    }
    
    if (root->right)
        get_modes(root->right, last, freq, max, modes, i);
}

void get_num_of_modes(struct TreeNode *root, double *last, int *freq, int max, int *returnSize)
{
    int val = root->val;
    
    if (root->left)
        get_num_of_modes(root->left, last, freq, max, returnSize);
    
    if (*last != val)
    {        
        *freq = 1;        
        *last = val;
    }
    else
        (*freq)++;
    
    if (*freq == max)
        (*returnSize)++;


    if (root->right)
        get_num_of_modes(root->right, last, freq, max, returnSize);
}

void get_max_freq(struct TreeNode *root, double *last, int *freq, int *max)
{
    int val = root->val;
    
    if (root->left)
        get_max_freq(root->left, last, freq, max);
    
    if (*last != val)
    {
        *freq = 1;
        *last = val;
    }
    else
        (*freq)++;

    if (*freq > *max)
        *max = *freq;
    
    if (root->right)
        get_max_freq(root->right, last, freq, max);
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findMode(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    
    int *modes = NULL;
    double last = -2147483649; // Out of int range to avoid 0 case
    int freq = 0;
    int max = 0;
    int i = 0;
    
    if (root == NULL)
        return NULL;
    
    get_max_freq(root, &last, &freq, &max);
    
    freq = 0;
    last = -2147483649;
    get_num_of_modes(root, &last, &freq, max, returnSize);

    freq = 0;
    last = -2147483649;
    modes = (int *)malloc(sizeof(int) * (*returnSize));
    get_modes(root, &last, &freq, max, modes, &i);
    
    return modes;
}

Validating Binary Search Tree (BST) in C

描述

驗證二元搜尋樹是否有效，有效的二元搜尋樹必須符合下列原則

• 左子樹的值小於根的值
• 右子樹的值大於根的值
• 左右子樹也是二元搜尋樹

範例

• 有效

無節點

單節點

    0
   / \

左右子樹

    2
   / \
  1   3

• 無效
有相同的值

    1
     \
     (1)

右子樹節點的值小於根的值

    10
   / \
  5   15
     / \
   (6)  20

左子樹節點的值大於根的值

    3
     \
     30
    /
   10
     \
     15
       \
      (45)

原理

用中序走訪(inorder traversal)二元搜尋樹取得節點的值會升冪排列，一旦走訪節點的值小於等於前面節點的值，就不是有效二元搜尋樹

實作

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

bool validate(struct TreeNode* root, double *last)
{   
    if (root->left)
        if (validate(root->left, last) == false)
            return false;
    
    // Check ascending order
    if (root->val > *last)
        *last = root->val;
    else
        return false;
    
    if (root->right)
        if (validate(root->right, last) == false)
            return false;
    
    // Subtree is valid
    return true;
}

bool isValidBST(struct TreeNode* root){  
    double last = -2147483649; // integer type minimum is -2147483648, last should be able to store integer minimum
    
    if (root == NULL)
        return true;

    return validate(root, &last);
}