二叉树 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 应该是

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

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

考虑一下案例：

          5
         / \
        2   1
       /    
      3

-谢谢

Answer 1

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

我相信原始代码对于 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

Answer 2

由于伯特没有修正他的答案，我将发布正确的答案。

是的，你是对的，原始代码已被破坏，尽管这里大多数人都这么说。在您的示例中，

      5
     / \
    2   1
   /    
  3

调用

hasPathSum(root, 7);

尽管没有添加到 7 的根到叶路径，但 仍将返回 true。这是因为当到达节点 2 时，它会递归检查右子节点（总和为 0），然后返回 true，因为右子节点为 null。

该修复的灵感来自 Bert 的回答：

// `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 块合并为一个长语句（大量的 and 和 ors），但我发现这样更干净。

Answer 3

嗨，大家好
感谢您的回答，这个讨论看起来很有趣，
昨晚我再次尝试实现这个功能，我认为我的解决方案适用于所有情况，

实际上我以更简单的方式实现，以便每个人都可以理解

---

有四种情况需要检查

1. 如果两个孩子 null（我们的目标情况）
2. 如果只有右子节点存在（意味着左子节点为空），则为
3. 如果只有左子节点存在（意味着右子节点为空）
4. 如果两个子节点都存在（意味着节点有左子节点和右子节点）

一个特殊的case：如果您直接将输入树作为 null 传递，则需要处理（如果块请求还需要一个。）

    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));
}

请查看我的代码
这适用于所有二叉树情况吗？和
如果需要任何更改，请告诉我。

-谢谢

Answer 4

对于以下简单情况，OP 的函数显然会失败：

   1
    \
     2

上面的树只是 sum 3 的一个根到叶路径。但是 OP 的函数将返回 true for 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

Answer 5

这是另一种方法，它计算每条路径的总和，并将其与目标值相匹配。恕我直言，这似乎比使用子和逻辑更直观。

此外，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;

}

Answer 6

试试这个

   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) ) );  
        }
   }