二叉树中目标对象出现次数的递归算法实现与验证求助

嘿，先给你点个赞——你的递归思路完全是对的！这个算法的核心逻辑没问题，但可以做些小优化让它更简洁易读，同时保持正确性。

原算法的正确性分析 #

你的算法逻辑是成立的：

• 遇到空节点直接返回0，这是递归的终止条件，没问题；
• 当前节点匹配目标对象时计数加1，再递归累加左右子树的计数，这个遍历逻辑能覆盖所有节点，不会遗漏。

不过原代码里的counter初始化后再判断加1的步骤有点冗余，我们可以简化一下。

优化后的算法 #

Algorithm count(Node, desiredObject)
    // 递归终止条件：空节点没有可计数的对象
    if Node is empty:
        return 0
    
    // 直接计算当前节点的匹配数，不用额外的变量初始化
    currentCount = 1 if Node's data equals desiredObject's data else 0
    
    // 递归遍历左右子树，获取子树中的目标计数
    leftCount = count(Node's left child, desiredObject)
    rightCount = count(Node's right child, desiredObject)
    
    // 返回当前节点计数 + 左右子树计数的总和
    return currentCount + leftCount + rightCount

优化点说明 #

• 去掉了多余的counter变量初始化，直接通过条件判断得到当前节点的计数，代码更简洁；
• 变量命名更语义化（currentCount替代counter），可读性更强；
• 保留了原算法的所有正确逻辑，边界情况（空树、单节点树、全匹配/全不匹配树）都能正确处理。

合理性补充 #

这个递归方案的时间复杂度是O(n)（每个节点恰好被访问一次），空间复杂度是O(h)（h为树的高度，平衡树是O(logn)，最坏情况如链表树是O(n)），这是二叉树遍历类问题的标准复杂度，完全合理。

内容的提问来源于stack exchange，提问作者user9427949