二叉树 hasPathSum() 实现

Question

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

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

考虑这种情况：

          5
         / \
        2   1
       /    
      3

-谢谢

Answer 1

您确实应该编写代码并尝试一下 - 这样您可以学到很多东西。（编辑：我当然是......）

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

编辑：

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

编辑：

我的新解决方案如下。请注意，所包含的 optimization( 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