返回bool与列表的二叉树路径递归函数工作原理解析

下方函数用于查找二叉树中到达指定节点的路径指令（"L"代表左方向，"R"代表右方向）：

def find(n: TreeNode, val: int, path: List[str]) -> bool:
    if n.val == val:
        return True
    if n.left and find(n.left, val, path):
        path += "L"
    elif n.right and find(n.right, val, path):
        path += "R"
    return path

我理解基准情况返回True的作用是终止递归，同时告知上层递归调用当前探索的分支最终可以找到目标值节点，但我不理解代码中return path的作用，存在以下两点疑问：

• 该递归函数同时返回布尔值和字符串列表两种不同类型的对象，其运行逻辑是怎样的？
• 代码中为什么要返回path？删除该行代码会得到错误结果，但我没有找到任何将该返回值赋值给变量使用的位置。

疑问解答 #

首先要明确：这个函数本身的类型标注是错的，属于Python动态类型特性下的不规范写法，它标注返回值为bool，实际混用了布尔值和列表作为返回值，所有返回值本质都是为了给上层递归的条件判断提供真假判断依据，没有真的在外部使用返回的列表对象。

关于混合返回值的运行逻辑 #

Python的条件判断不会校验对象类型，任何对象都可以被判定为真/假：True、非空列表属于真值，False、None、空列表属于假值。这个函数的返回值逻辑完全围绕递归分支判断设计：

• 只有递归走到目标节点时，才会返回布尔值True，这个返回值直接被上一层的if n.left and find(...)/elif n.right and find(...)捕获，用来确认「当前子树存在目标节点，需要追加对应方向字符」。
• 其余所有场景，函数都会走到最后一行返回path列表：如果当前分支没找到目标，path是空列表（假值），上层收到假值就会知道当前分支走不通，转而探索其他分支；如果当前分支已经完成方向字符追加，path是非空列表（真值），上层收到真值就会知道目标已经找到，不需要再探索其他分支，继续向上回溯追加路径。

关于return path的实际作用 #

你觉得这个返回值没被使用，是因为忽略了递归回溯链路里的真假传递需求：
如果删掉最后一行return path，Python函数默认返回None（假值），会直接打断递归的正确判断流程：

1. 当某一层递归确认左/右子树找到目标，执行完path += "L"/path += "R"后，函数没有显式返回值，就会向上层返回None
2. 上层的条件判断收到None（假值），会误以为当前分支没有找到目标，错误地进入另一个分支重复探索，要么把已经拼对的路径打乱，要么最后返回找不到目标的错误结果。

说白了这个写法是作者图省事：本来在path += "L"和path += "R"后面各加一行return True，逻辑会更清晰，也不会出现类型混乱的问题；但作者靠最后返回path的真假值，省掉了这两行return True，用非空path的真值替代了True的判断作用，才写出了这种看起来很绕的实现。

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