简单的二叉树 DFS 递归代码提前停止而不是遍历整棵树

Question

我试图沿着二叉树向下走，寻找目标 TreeNode，然后 return 当我找到它时那个节点。我的代码是：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def findTarget(self, root: TreeNode, target: TreeNode) -> TreeNode:
        # base case 
        if root.val == target.val:
            return root
        if root.left:
            return self.findTarget(root.left, target)        
        if root.right:
            return self.findTarget(root.right, target)
        return None

但是对于看起来像这样的树，我正在寻找节点 5：

我的代码只遍历节点 1、2、4、8。我错过了什么？我想一旦它到达节点 8，它就会看到它没有左节点也没有右节点并且 return None 返回到节点 4 的左节点调用。之后，节点 4 将查看根的右侧，即 9。但它只是停在 8?

我在网上看到了其他解决方案，我只是好奇我在这个特定案例中犯了什么错误。

Answer 1

class Solution:
    def findTarget(self, root: TreeNode, target: TreeNode) -> TreeNode:
        # base case 
        if root.val == target.val:
            return root
        maybe = None
        if root.left:
            maybe = self.findTarget(root.left, target)
        if not maybe and root.right:
            maybe = self.findTarget(root.right, target)
        return maybe

Answer 2

您的第一个分支是 if root.left: return ...。这意味着即使有右子树和左子树，即使左子树没有匹配结果，你也永远不会探索右子树。

将其变成“或”逻辑：如果左子递归调用找到匹配的节点，则可以立即return。如果在左子树中没有找到结果，暂时不要return。探索正确的子树，看看是否找到任何东西。

顺便说一句，我认为检查子节点的特征是一种不优雅的递归反模式，并且容易产生混乱和细微的错误。在对当前节点进行操作之前检查当前节点的空状态，而不是子节点的空状态。让递归处理这些检查。

class Solution:
    def findTarget(self, root: TreeNode, val: int) -> TreeNode:
        if root:
            if root.val == val:
                return root
            
            return (self.findTarget(root.left, val) or 
                    self.findTarget(root.right, val))

简单的二叉树 DFS 递归代码提前停止而不是遍历整棵树

Simple binary tree DFS recursion code is stopping early and not walking full tree

python

recursion

binary-tree