二叉树递归遍历中使用return无法终止的问题咨询

怎么改才能在J节点停止？ #

要让整个遍历流程停下来，得让递归函数返回一个「是否要停止」的信号，上层调用收到这个信号后立刻终止后续操作。修改后的代码如下：

class TreeNode:
    """
    Representing a tree node consisting of
    datum: the datum stored at the node
    left: reference to the left child node
    right: reference to the right child node
    """

    def __init__(self, datum, left, right):
        self.datum = datum
        self.left = left
        self.right = right

    def inorder_Node(self):
        # 先处理左子树，如果左子树返回停止信号，直接往上传
        if self.left is not None:
            if self.left.inorder_Node():
                return True
        
        print(self.datum)
        # 碰到J节点，返回停止信号
        if self.datum == "J":
            return True
        
        # 处理右子树，同理收到停止信号就往上传
        if self.right is not None:
            if self.right.inorder_Node():
                return True
        
        # 没碰到停止条件，返回继续信号
        return False

class MyBinaryTree:
    """
    Implementation of a binary tree
    """

    def __init__(self):
        self.rootNode = None

    def print_in_order(self):
        if self.rootNode is not None:
            self.rootNode.inorder_Node()

# 构建二叉树部分不变
node_d = TreeNode(datum="D", left=None, right=None)
node_i = TreeNode(datum="I", left=None, right=None)
node_j = TreeNode(datum="J", left=None, right=None)
node_k = TreeNode(datum="K", left=None, right=None)
node_l = TreeNode(datum="L", left=None, right=None)
node_m = TreeNode(datum="M", left=None, right=None)
node_e = TreeNode(datum="E", left=node_i, right=node_j)
node_f = TreeNode(datum="F", left=node_k, right=node_l)
node_h = TreeNode(datum="H", left=node_m, right=None)
node_b = TreeNode(datum="B", left=node_d, right=node_e)
node_c = TreeNode(datum="C", left=node_f, right=node_h)
node_a = TreeNode(datum="A", left=node_b, right=node_c)
tree = MyBinaryTree()
tree.rootNode = node_a
tree.print_in_order()

修改后的逻辑说明 #

• 每个inorder_Node()返回布尔值：True代表需要停止遍历，False代表继续。
• 遍历左/右子树时，只要子树返回True，立刻向上传递停止信号，不再执行后续代码。
• 打印当前节点后，检查是否是目标节点J，若是则返回True触发停止流程。
• 这样停止信号会顺着递归调用栈一路往上传递，整个遍历流程会在打印J后立刻终止。

运行修改后的代码，输出结果为：

D
B
I
E
J

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