递归实现树中指定值节点最大深度函数返回值异常排查

你的代码返回0的核心原因是混淆了两个完全不同的概念：节点在原树中的深度，和以该节点为根的子树的深度。题目要求的是前者（找到值为value的节点在整个树中的最大深度），但你的代码实现的是后者（计算目标节点作为根的子树的最大深度）。

你的代码逻辑问题拆解 #

我们拿你的测试用例一步步走一遍：

1. 根节点是1（不是目标值2），所以返回max(left_result, right_result)
2. 左子树是节点2（目标值）：
   • 它的左右子树都是None，递归返回-1
   • 因为当前节点是目标值，执行1 + max(-1, -1) → 0
3. 右子树是节点3（不是目标值），返回max(left_result, right_result)
   • 它的左子树是None，返回-1
   • 右子树是节点2（目标值），同样计算得到0
   • 所以节点3返回max(-1, 0) → 0
4. 最终根节点返回max(0, 0) → 0，这就是你得到的结果

正确思路与修正代码 #

要解决“找到树中值为value的节点的最大深度”，我们需要在遍历树的过程中跟踪当前节点的深度，遇到目标值时记录这个深度，最后取所有记录中的最大值。

修正后的代码实现 #

class TN:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def max_depth(t, value):
    # 辅助递归函数，传递当前节点的深度
    def helper(node, current_depth):
        if not node:
            # 空节点，没有目标值，返回-1表示无效深度
            return -1
        # 初始化当前子树的最大深度：如果当前节点是目标，初始值为当前深度，否则为-1
        current_max = current_depth if node.value == value else -1
        # 递归遍历左右子树，深度+1
        left_max = helper(node.left, current_depth + 1)
        right_max = helper(node.right, current_depth + 1)
        # 返回当前子树中找到的最大深度
        return max(current_max, left_max, right_max)
    
    # 根节点的深度从0开始（符合你例子的预期），如果需要从1开始可以改成1
    result = helper(t, 0)
    # 如果没有找到目标节点，返回0或者根据需求调整，这里按例子返回有效深度
    return result if result != -1 else 0

# 构建测试树
tree4 = TN(2)
tree3 = TN(3, left=None, right=tree4)
tree2 = TN(2)
tree1 = TN(1, left=tree2, right=tree3)

print(max_depth(tree1, 2))  # 输出：2

逻辑解释 #

1. 辅助函数helper：负责递归遍历树，同时传递当前节点的深度（从根节点的0开始）
2. 空节点处理：空节点没有目标值，返回-1表示该路径没有有效深度
3. 当前节点判断：如果当前节点是目标值，就把当前深度作为候选最大值；否则初始候选值为-1
4. 递归遍历：分别遍历左右子树，深度加1，获取左右子树中目标节点的最大深度
5. 取最大值：比较当前节点的候选深度、左子树最大深度、右子树最大深度，返回最大的那个
6. 边界处理：如果整棵树都没有目标节点，返回0（你可以根据需求改成-1或者其他值）

补充说明 #

如果你的深度定义是“根节点深度为1”（即节点所在的层数），只需要把调用helper时的current_depth从0改成1，此时测试用例会返回3，你可以根据实际需求调整。

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