java - 二进制搜索树打印路径

Question

我在尝试创建到 TreeNode 的打印路径时遇到了一点困难方法。不太确定我哪里出错了，但我认为它可能在第二个 else .

代码:

public static ArrayList<Integer> printPath(TreeNode node, ArrayList<Integer> path, int value) {
        if (node == null) {
            return path;
        } else {
            if (node.data == value) {
                path.add(value);
                return path;
            } else {
                path.add(node.data);
                printPath(node.left, path, value);
                printPath(node.right, path, value);
            }
        }
        return path;
    }

目前我得到的输出为 [20, 8, 4, 12, 22]当我应该只得到 [20,8,12] .

我在图片中添加了二叉搜索树，路径为空ArrayList , 值为 12

Answer 1

假设你只想要从 root-Node 到给定的 value 的最短路径，你必须将这个值与当前节点的数据进行比较，然后决定是否走向左或向右(而不是两个方向)。

public static ArrayList<Integer> printPath(TreeNode node, ArrayList<Integer> path, int value) {
    if (node == null)
        return path;

    path.add(node.data);

    int cmp = Integer.compare(value, node.data);

    if (cmp < 0) // value is smaller, so go left
        printPath(node.left, path, value);
    else if (cmp > 0) // value is larger, so go right
        printPath(node.right, path, value);
    else /* if (cmp == 0) */
         return path; // value found

    return path;
}

这应该在调用时为建议的树提供 [20, 8, 12]:

printPath(root, new ArrayList<Integer>(), 12);