代码之家 › 专栏 › 技术社区 › Preetam Purbia

二叉树hasPathSum()实现

binary-tree tree data-structures algorithm java

Preetam Purbia · 技术社区 · 14 年前

您好! 我在努力实现 hasPathSum() 对于给定的编号,根到叶节点之间存在任何路径。

我从斯坦福大学的网站上得到这个密码。我认为这是错误的

/** 
 Given a tree and a sum, returns true if there is a path from the root 
 down to a leaf, such that adding up all the values along the path 
 equals the given sum. 
 Strategy: subtract the node value from the sum when recurring down, 
 and check to see if the sum is 0 when you run out of tree. 
*/ 

boolean hasPathSum(Node node, int sum) { 
  // return true if we run out of tree and sum==0 
  if (node == null){ 
    return(sum == 0); 
  } 
  else { 
  // otherwise check both subtrees 
    int subSum = sum - node.data; 
    return(hasPathSum(node.left, subSum) || hasPathSum(node.right, subSum)); 
  }

这是正确的实施吗?

我在想这个如果应该是

if(node.left==null&node.right==null)

如果我错了,请澄清我的困惑

考虑这个案例:

-谢谢

6 回复 | 直到 13 年前

Bert F 14 年前

你真的应该把它编码并尝试一下-这样你会学到很多东西。( 编辑:我当然是。。。 )

我相信原始代码失败了 hasPathSum(tree, 7) 因为节点2不是叶。

编辑:

由于明显的错误而被撤销的原始代码-至少对除了我以外的所有人都是如此:-)

编辑:

我的新解决方案如下。注意,包含的优化( if (sum <= node.data) ) 假设树是由所有 积极的 数据值 . 如果树的数据值为零或负,则应删除或调整该树。(感谢马克·彼得斯)。

同时注意回答中关于处理的讨论 hasPathSum(null, 0) .

static boolean hasPathSumBert(final Node node, final int sum) {
    // return true if we run out of tree and sum==0
    if (node == null) {                                   // empty tree
        // choose one:
        return (sum == 0);
        //return false;
    } else if (node.left == null && node.right == null) { // leaf
        return (sum == node.data);
    } else if (sum <= node.data) {                        // sum used up
        return false;
    } else {                                              // try children
        return (node.left != null  && hasPathSumBert(node.left, sum - node.data)) ||
               (node.right != null && hasPathSumBert(node.right, sum - node.data));
    }
}

完整代码:

public class TreeTest {
    static class Node {
        int data;
        Node left;
        Node right;

        Node(final int data, final Node left, final Node right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(final String[] args) {
        final Node three = new Node(3, null, null);

        final Node two = new Node(2, three, null);
        final Node one = new Node(1, null, null);

        final Node five = new Node(5, two, one);
        final Node tree = five;

        for (int i = 0; i <= 10; i++) {
            System.out.println(i + "");
            System.out.println("original = " + hasPathSum(tree, i));
            System.out.println("bert     = " + hasPathSumBert(tree, i));
            System.out.println("mark     = " + hasPathSumMark(tree, i));
            System.out.println();
        }

        System.out.println("hasPathSumBert(null, 0): "+ hasPathSumBert(null, 0));
        System.out.println("hasPathSumBert(null, 1): "+ hasPathSumBert(null, 1));
    }

    static boolean hasPathSum(final Node node, final int sum) {
        // return true if we run out of tree and sum==0
        if (node == null) {
            return (sum == 0);
        } else {
            // otherwise check both subtrees
            final int subSum = sum - node.data;
            return (hasPathSum(node.left, subSum) || hasPathSum(node.right, subSum));
        }
    }

    static boolean hasPathSumBert(final Node node, final int sum) {
        // return true if we run out of tree and sum==0
        if (node == null) {                                   // empty tree
            // choose one:
            return (sum == 0);
            //return false;
        } else if (node.left == null && node.right == null) { // leaf
            return (sum == node.data);
        } else if (sum <= node.data) {                        // sum used up
            return false;
        } else {                                              // try children
            return (node.left != null  && hasPathSumBert(node.left, sum - node.data)) ||
                   (node.right != null && hasPathSumBert(node.right, sum - node.data));
        }
    }

    static boolean hasPathSumMark(final Node node, final int sum) {
        final int subSum = sum - node.data;
        if (node.left == null && node.right == null) {
            return (subSum == 0);
        } else {
            // otherwise check both subtrees
            if (node.left != null  && hasPathSumMark(node.left, subSum))
                return true;
            if (node.right != null && hasPathSumMark(node.right, subSum))
                return true;
            return false;
        }
    }
}

样本运行:(注案例7)

0
original = false
bert     = false
mark     = false

1
original = false
bert     = false
mark     = false

2
original = false
bert     = false
mark     = false

3
original = false
bert     = false
mark     = false

4
original = false
bert     = false
mark     = false

5
original = false
bert     = false
mark     = false

6
original = true
bert     = true
mark     = true

7
original = true
bert     = false
mark     = false

8
original = false
bert     = false
mark     = false

9
original = false
bert     = false
mark     = false

10
original = true
bert     = true
mark     = true

hasPathSumBert(null, 0): true
hasPathSumBert(null, 1): false

Mark Peters 14 年前

既然伯特没有回答他的问题,我会把答案放在正确的地方。

是的,你说的没错,尽管这里的大多数人都在说,原始代码已经被破坏了。在你的例子中

打电话

hasPathSum(root, 7);

会回来的 true 尽管事实上没有根到叶的路径增加到7。因为当node 2 到达时,它递归地检查正确的子项(和为0),然后返回true,因为正确的子项是 null .

修正的灵感来自伯特的回答:

// `if` statement should check children and `return` statement deduct node.data from sum
boolean hasPathSum(Node node, int sum) { 
  int subSum = sum - node.data; 
  if(node.left==null && node.right==null) { 
    return(subSum == 0); 
  } 
  else { 
    // otherwise check both subtrees 
    if ( node.left != null && hasPathSum(node.left, subSum) ) {
        return true;
    if ( node.right != null && hasPathSum(node.right, subSum) ) {
        return true;
    }
    return false;
  } 
}

如果需要的话,可以将else块卷成一个长语句(有很多ands和or),但是我发现这个更干净。

Preetam Purbia 14 年前

嗨,伙计们谢谢你的回答,这个讨论看起来很有趣, 昨晚我再次尝试实现这个功能,我想我的解决方案对所有的情况都有效,

实际上,我是以更简单的方式实现的,这样每个人都可以理解

有四个案子要查

如果两个孩子都是空的(我们的目标案例)
如果只有右子存在(意味着左子为零)
如果只有左子存在(意味着右子是空)
如果两个孩子都存在(意味着节点有左右两个孩子)

一个特例 :如果直接将输入树作为空值传递,则需要处理(如果需要块,则需要再处理一个)

    public static boolean hasPathSum(TNode root, int sum)
{
    if(root==null) //it is called only if you pass directly null
    return false;

    int subsum = sum-root.data;
    //if(subsum<0) return false; //uncomment this for reducing calls for negative numbers
    if(root.left==null && root.right==null) //for leaf node
    return (subsum==0);

    if(root.left==null) //if only right child exist
    return hasPathSum(root.right, subsum);

    if(root.right==null)//if only left child exist
    return hasPathSum(root.left, subsum);

    return (hasPathSum(root.left, subsum) || hasPathSum(root.right,subsum));
}

请检查我的代码这对所有的二叉树情况都有效吗?和如果需要更改,请告诉我。

-谢谢

codaddict 13 年前

在以下简单情况下,OP的功能显然失效:

   1
    \
     2

上面的树只是一个根到叶的总和路径 3 . 但是OP的函数将返回true hasPathSum(root,1)

这是因为 只有当我们到达一个叶节点(空的左子树和空的右子树)或一个空树的特殊情况时,变化的子和才应该比较为零。

OP的功能是用 NULL 像叶子一样的孩子。

以下功能(与Mark的+一个附加检查相同)将其修复:

boolean hasPathSum(Node node, int sum) {
        // CASE 1: empty tree.
        if (node == NULL) {
                return sum == 0;
        }
        // CASE 2: Tree exits.
        int subSum = sum - node.data;
        // CASE 2A: Function is called on a leaf node.
        if (node.left==null && node.right==null) {
                return subSum == 0;
        // CASE 2B: Function is called on a non-leaf node.
        } else {
                // CASE 2BA: Non-left node has desired path in left subtree.
                if (node.left != null && hasPathSum(node.left, subSum) ){
                        return true;
                }
                // CASE 2BB: Non-left node has desired path in right subtree.
                if ( node.right != null && hasPathSum(node.right, subSum) ) {
                        return true;
                }
                // CASE 2BC: Non-left node has no desired pat.
                return false;
        }
}

C版: Ideone Link

Azeem 10 年前

这里有一种替代方法,可以计算每条路径的总和,并将其与目标值匹配。嗯,这似乎比使用子系统的逻辑更直观。

此外,nums列表将存储所有根到叶路径的总和。我添加这个只是为了确保我的代码没有生成任何不需要的路径。

public static boolean hasPathSum(Node root, int sum, int val, ArrayList<Integer> nums) {
    if(root == null) {
        return (sum == 0);
    }

    val = val + root.data;

    if(root.right == null && root.left == null) {
        nums.add(val);
        return (val == sum);
    }

    boolean left = hasPathSum(root.left, sum, val, nums);
    boolean right = hasPathSum(root.right, sum, val, nums);

    return left || right;

}

Prasanna Kumar H A 8 年前

试试这个

   bool hasPathSum(struct node* node, int sum){
        if(node == NULL){       
           return false;  
        }
        if((sum - (node->data) == 0) && (node->left == NULL) && (node->right == NULL) ) {    
            return true;  
        }
        if (sum - (node->data) < 0)  { 
            return false;  
        } else {       
            return( hasPathSum (node->left,sum - ( node->data ) ) || hasPathSum (node->right, sum - (node->data) ) );  
        }
   }