我在尝试创建到 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
最佳答案
假设你只想要从 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);
关于java - 二进制搜索树打印路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25022410/