我怎样才能加快我的最小二叉树深度函数？

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

Answer 1

正如评论中所指出的，如果您保存 return 值，则可以节省多次调用：

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

当我测试它时，它在 Leetcode 上给了我 4 毫秒的运行时间。

Answer 2

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

我怎样才能加快我的最小二叉树深度函数？

How can I speed up my minimum-depth-of-binary-tree function?

c

optimization

binary-tree

binary-search-tree