使用Leap Of Faith求解二叉树节点到根路径时结果错误求排查

问题根因分析 #

代码的核心错误在else分支的处理逻辑：没有判断右子树的查询结果是否为空，就直接往结果列表中添加了当前节点的值，导致子树中不存在目标节点时，也会错误返回包含当前节点的非空列表，误导上层逻辑判定左子树已经找到目标。

你给出的示例中错误执行流程如下：

查询目标值3时：

1. 根节点1不是目标，优先查询左子树2
2. 节点2不是目标，查询它的左子树返回空列表，进入else分支
3. 查询节点2的右子树返回空列表，原代码直接把节点2的值加入空列表，返回[2]
4. 根节点1拿到左子树返回的非空列表，误以为左子树找到了目标，直接把1加入列表返回，最终得到[2,1]，反转输出后就是你看到的错误结果{1,2}

修复后的代码 #

调整右子树查询后的逻辑，只有右子树查询到非空结果时，才添加当前节点值返回即可：

public static ArrayList<Integer> nodeToRootPath(Node root, int data) {
    ArrayList<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    if (root.data == data) {
        res.add(data);
        return res;
    }
    res = nodeToRootPath(root.left, data);
    if (res.size() != 0) {
        res.add(root.data);
        return res;
    }
    // 左子树未找到，查询右子树后先判空再处理
    res = nodeToRootPath(root.right, data);
    if (res.size() != 0) {
        res.add(root.data);
        return res;
    }
    // 左右子树都未找到，返回空列表
    return res;
}

如果需要返回从根到节点的正序路径，将最终结果列表反转即可。

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