给定一个二进制搜索树和一个目标值,找到所有路径(如果存在多个路径),它们加起来就是目标值。它可以是树中的任何路径。它不一定要从根开始。
例如,在下面的二进制搜索树中:
2
/ \
1 3
当和应为6时,应打印路径1 -> 2 -> 3
。
发布于 2011-01-04 18:03:11
从根开始遍历树,并对所有路径和进行后序收集。使用哈希表来存储可能的路径,这些路径以节点为根,并且仅向下移动。我们可以从节点本身及其子节点的路径中构造所有经过该节点的路径。
下面是实现上述功能的psuedo-code,但只存储和而不存储实际路径。对于路径本身,您需要将结束节点存储在哈希表中(我们知道它从哪里开始,并且在树中的两个节点之间只有一条路径)。
function findsum(tree, target)
# Traverse the children
if tree->left
findsum(tree.left, target)
if tree->right
findsum(tree.right, target)
# Single node forms a valid path
tree.sums = {tree.value}
# Add this node to sums of children
if tree.left
for left_sum in tree.left.sums
tree.sums.add(left_sum + tree.value)
if tree.right
for right_sum in tree.right.sums
tree.sums.add(right_sum + tree.value)
# Have we formed the sum?
if target in tree.sums
we have a path
# Can we form the sum going through this node and both children?
if tree.left and tree.right
for left_sum in tree.left.sums
if target - left_sum in tree.right.sums
we have a path
# We no longer need children sums, free their memory
if tree.left
delete tree.left.sums
if tree.right
delete tree.right.sums
这没有利用树是搜索树的事实,所以它可以应用于任何二叉树。
对于大树,哈希表的大小将变得难以控制。如果只有正值,则使用按和索引的数组可能更有效。
发布于 2015-11-07 15:21:48
老问题,但这里是我的尝试-应该是O(n)时间,因为你只访问每个节点一次:
public static List<ArrayList<Integer>> pathSum(Node head, int sum) {
List<Integer> currentPath = new ArrayList<Integer>();
List<ArrayList<Integer>> validPaths = new ArrayList<ArrayList<Integer>>();
dfsSum(head, sum, currentPath, validPaths);
return validPaths;
}
public static void dfsSum(Node head, int sum, List<Integer> currentPath, List<ArrayList<Integer>> validPaths) {
if (head == null) return;
currentPath.add(head.val);
if (head.left == null && head.right == null && sum == head.val) {
validPaths.add(new ArrayList<Integer>(currentPath));
}
dfsSum(head.left, sum - head.val, new ArrayList<Integer>(currentPath), validPaths);
dfsSum(head.right, sum - head.val, new ArrayList<Integer>(currentPath), validPaths);
}
和节点类:
class Node {
public int val;
public Node left;
public Node right;
public Node(int val) {
this.val = val;
}
}
https://stackoverflow.com/questions/4591763
复制相似问题