求树的结点个数，我这样写为啥不行，感觉和求树的高差不多

求树的结点个数，我这样写为啥不行，感觉和求树的高差不多

img


完整代码：

int NodeNum(BTNode* b)
{
    int lnum, rnum;
    if (b == NULL)
    {
        return 0;
    }
    else
    {
        NodeNum(b->lchild);
        NodeNum(b->rchild);
        return lnum + rnum;
    }
}


int NodeNum(BTNode* b)
{
    int lnum, rnum;
    if (b == NULL)
    {
        return 0;
    }
    else
    {
        lnum = NodeNum(b->lchild);
        rnum = NodeNum(b->rchild);
        return lnum + rnum + 1;
    }
}
  • 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7462703
  • 这篇博客你也可以参考下：求因数的高效算法
  • 除此之外, 这篇博客: 二分法求解两个有序数组的中位数，竟然如此高效！中的 思路一（常规法） 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

  • 定义两个索引，分别从两个数组的其实位置开始往后遍历，当遍历到中间位置时，即可取的中位数。

    图示：

    代码实现（含详细注释）：

    /**
 * 常规法
 * @param nums1 数组1
 * @param nums2 数组2
 * @return 中位数
 * 公众号：算法之灵魂拷问
 */
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int length1 = nums1.length;
    int length2 = nums2.length;
    //计算两个数组总长度
    int totalLength = length1 + length2;
    //标示中间数中比较小的一个数
    int middle1 = Integer.MIN_VALUE;
    //标示中间数中比较大的一个数
    int middle2 = Integer.MIN_VALUE;
    //数组1的索引，用于遍历数组1
    int index1 = 0;
    //数组2的索引，用于遍历数组2
    int index2 = 0;
    for (int i = 0; i <= totalLength / 2; i++) {
        //将稍大的中间值复制给较小的中间值，因为即将到来一个更大的
        middle1 = middle2;
        //使用数组1中的元素的前提是数组1没有越界并且数组1在该位置的元素小于数组2或者数组2已越界
        if (index2 >= length2 || (index1 < length1 && nums1[index1] < nums2[index2])) {
            //从数组1中取值，作为较大的中间值
            middle2 = nums1[index1++];
        } else {
            //从数组2中取值，作为较大的中间值
            middle2 = nums2[index2++];
        }
    }
    //如果总元素个数是偶数，那么取两数的平均值
    if ((totalLength % 2) == 0){
        return (middle1 + middle2) / 2.0;
    } else{
        //否则直接取较大的中间数即可
        return middle2;
    }
}

    注：关键点在于找对中间位置即可，当m+n为基数时，中位数即为第(m+n) / 2 + 1个元素的值，当m+n为偶数时， 为第(m+n)/2个元素与第(m+n)/2+1个元素的平均数

    提交代码后，虽然运行成功，但是仔细观察一下，这个思路的时间复杂度为O((m+n)/2)，也就是O(m+n)的复杂度，很明显并不符合题目中O(log(m + n))的要求，所以，可以再尝试一下其他思路。

  • 您还可以看一下 易文星老师的手把手教你实现人脸识别支付系统课程中的 高效的图像检索：引入随机性小节, 巩固相关知识点
  • 以下回答由chatgpt基于相关博客总结生成:

    该代码使用的是Java语言。该代码的目的是将阿拉伯数字转换为罗马数字。问题在于该代码占用的空间较大，需要进行优化。没有遇到明显的错误或异常。 这里提供一个可能的优化方案，从代码效率上入手，使得代码具有更高的效率，减少占用的空间。

    public class RomanDemo {
    public static void main(String[] args) {
        intToRoman(56);
    }

    public static String intToRoman(int num) {
        StringBuilder stringBuilder = new StringBuilder();
        int[] ints = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        for (int i = 0; i < ints.length; i++) {
            while (num >= ints[i]) {
                num -= ints[i];
                stringBuilder.append(romans[i]);
            }
        }
        return stringBuilder.toString();
    }
}

    此代码的思路是将常见的组合记录在两个数组中，分别记录阿拉伯数字和对应的罗马数字，然后运用循环结构依次匹配，直到所有的阿拉伯数字已经转换完毕。

    1.先定义了两个字符串数组，$ints$用于记录阿拉伯数字和对应的罗马数字，分别为$1000,900,500,400,100,90,50,40,10,9,5,4,1$和$M,CM,D,CD,C,XC,L,XL,X,IX,V,IV,I$。该数组中前7个元素中蕴含了一些常见的组合规则，比如900，即CM表示的是$900=1000-100=CM$，也可用$DCCCC$表示，但这显然不是最优选择。通过这种记录方法，可以直接枚举所有可能遇到的组合情况。 2.在循环中以从大到小的顺序分别匹配，在循环中用while判断$num$是否大于等于记录在数组中的数字，如果是，就累加罗马数字； 3.一直迭代，直到$num$小于$ints[i]$为止，将结果返回。

    这种方法在速度和空间上均有优化，具有更优秀的性能表现。