Как я могу ускорить свою функцию минимальной глубины двоичного дерева? - PullRequest
Новая
       46

Как я могу ускорить свою функцию минимальной глубины двоичного дерева?

0 голосов
/ 21 декабря 2018

Я пытаюсь повысить эффективность своего кода и пытаюсь решить проблему дерева минимальной глубины, используя метод рекурсии, но я не уверен, что это лучший способ решения проблемы.Я получил быстрее, чем 6% кодеров на LeetCode, но не могу улучшить его больше, чем это. 

int minDepth(struct TreeNode* root) {

    if(root == NULL){
        return 0;
    }
    if(root->left == NULL && root->right == NULL){
        return 1;
    }
    if(!root->left){
        return minDepth(root->right) + 1;
    }
    if(!root->right){
        return minDepth(root->left)+1;
    }
    if(minDepth(root->right) > minDepth(root->left)){
        return minDepth(root->left) + 1;
    }else{
        return minDepth(root->right) + 1;
    }
}

Ответы [ 2 ]

0 голосов
/ 21 декабря 2018

близкое решение с предыдущим, но с меньшим сравнением с 0 (по сравнению с Osiris) или рекурсивными вызовами (по сравнению с lvella) 

int minDepth(struct TreeNode* root) {
  if (root == NULL){
    return 0;
  }

  if(root->left == NULL) {
    return (root->right == NULL) ? 1 : minDepth(root->right) + 1;
  }

  if(root->right == NULL) {
    return minDepth(root->left) + 1;
  }

  int r = minDepth(root->right);
  int l = minDepth(root->left);

  return ((r > l) ? l : r) + 1;
}

конечно if (root == NULL) полезно только для первого вызова, но дляудалить его нужно чтобы было 2 функции

0 голосов
/ 21 декабря 2018

Как указано в комментариях, вы можете сэкономить несколько вызовов, если сохраните возвращаемое значение: 

int minDepth(struct TreeNode* root) {

    if(root == NULL){
        return 0;
    }
    if(root->left == NULL && root->right == NULL){
        return 1;
    }

    int minDepth_left = minDepth(root->left);
    int minDepth_right = minDepth(root->right);

    if(!root->left){
        return minDepth_right+1;
    }
    if(!root->right){
        return minDepth_left+1;
    }
    if(minDepth_right > minDepth_left){
        return minDepth_left + 1;
    }else{
        return minDepth_right + 1;
    }
}

Когда я проверял его, он давал мне время выполнения 4 мс на Leetcode.

...