java - 二叉树 hasPathSum() 实现

你好
我正在尝试实现 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)

如果我错了请清除我的困惑

考虑这种情况:

-谢谢

最佳答案

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

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

编辑:

由于明显错误而撤回了原始代码 - 至少对除我之外的所有人来说都是显而易见的 :-)

编辑:

我的新解决方案如下。请注意，包含的优化 ( if (sum <= node.data) ) 假设树由所有正数据值组成。如果树具有零或负数据值，则应删除或调整它。 (感谢@Mark Peters)。

另请注意有关处理 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

关于java - 二叉树 hasPathSum() 实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4214859/