首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >在二进制搜索树中查找对目标值求和的路径

在二进制搜索树中查找对目标值求和的路径
EN

Stack Overflow用户
提问于 2011-01-04 16:30:30
回答 2查看 12.9K关注 0票数 18

给定一个二进制搜索树和一个目标值,找到所有路径(如果存在多个路径),它们加起来就是目标值。它可以是树中的任何路径。它不一定要从根开始。

例如,在下面的二进制搜索树中:

代码语言:javascript
复制
  2
 / \ 
1   3 

当和应为6时,应打印路径1 -> 2 -> 3

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2011-01-04 18:03:11

从根开始遍历树,并对所有路径和进行后序收集。使用哈希表来存储可能的路径,这些路径以节点为根,并且仅向下移动。我们可以从节点本身及其子节点的路径中构造所有经过该节点的路径。

下面是实现上述功能的psuedo-code,但只存储和而不存储实际路径。对于路径本身,您需要将结束节点存储在哈希表中(我们知道它从哪里开始,并且在树中的两个节点之间只有一条路径)。

代码语言:javascript
复制
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

这没有利用树是搜索树的事实,所以它可以应用于任何二叉树。

对于大树,哈希表的大小将变得难以控制。如果只有正值,则使用按和索引的数组可能更有效。

票数 12
EN

Stack Overflow用户

发布于 2015-11-07 15:21:48

老问题,但这里是我的尝试-应该是O(n)时间,因为你只访问每个节点一次:

代码语言:javascript
复制
  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);
  }

和节点类:

代码语言:javascript
复制
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node(int val) {
      this.val = val;
    }
  }
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/4591763

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档