c - 如何加快我的最小深度二叉树函数？

Question

我正在尝试提高代码效率，并且正在尝试使用递归方法解决最小深度树问题，但我不确定这是否是解决问题的最佳方法。我在 LeetCode 上比 6% 的程序员都快，但不能再改进了。

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;
    }
}

标签： coptimizationbinary-treebinary-search-tree

Answer 1

与以前的解决方案接近，但与 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 个函数