C++二叉树hasPathSum函数实现求助：根到叶路径和判断

Hey there! Let's work through this problem together. I notice you're stuck on two key points: handling the TreeNode* parameter instead of a BinaryTree instance, and figuring out the recursive logic for checking root-to-leaf path sums. Let's break this down step by step, without modifying the required hasPathSum() function signature.

First: Fix the isLeaf() Method #

First off, your TreeNode class has an isLeaf() declaration but no implementation. We need this to identify leaf nodes (nodes with no children). Add this implementation inside the TreeNode class in TreeNode.h:

bool isLeaf() {
    return leftlink == nullptr && rightLink == nullptr;
}

Second: Understand the Recursive Logic for hasPathSum() #

The recursive approach relies on reducing the problem size at each step:

• Base Case 1: If the current TreeNode* is NULL, return 0 (false) — since an empty tree has no root-to-leaf paths, per the problem statement.
• Base Case 2: If the current node is a leaf, check if its value equals the remaining sum we're looking for. If yes, return 1 (true); else, return 0.
• Recursive Step: For non-leaf nodes, subtract the current node's value from the target sum, then recursively check if either the left or right subtree has a path that sums up to this remaining value. If either recursive call returns true, return 1.

Third: Implement the hasPathSum() Function #

Here's the full implementation for the hasPathSum(TreeNode*, int) method in BinaryTree.cpp:

int BinaryTree::hasPathSum(TreeNode * tree, int sum) {
    // Empty node: no valid path exists
    if (tree == nullptr) {
        return 0;
    }

    // Check if current leaf node matches the remaining sum
    if (tree->isLeaf()) {
        return (tree->data == sum) ? 1 : 0;
    }

    // Calculate remaining sum after including current node's value
    int remainingSum = sum - tree->data;

    // Recursively check left and right subtrees — if either has a valid path, return true
    return hasPathSum(tree->leftlink, remainingSum) || hasPathSum(tree->rightLink, remainingSum);
}

Fourth: Handle the TreeNode* Parameter Issue #

Since the root of your BinaryTree is a private member, you can't directly pass it to hasPathSum() from main(). To fix this without modifying the original function's signature, add an overloaded public method to your BinaryTree class that wraps the recursive call:

Update BinaryTree.h #

Add this declaration to the public section of BinaryTree:

int hasPathSum(int sum); // New public interface to call the recursive version

Update BinaryTree.cpp #

Implement the overloaded method:

int BinaryTree::hasPathSum(int sum) {
    // Call the recursive function with the root node
    return hasPathSum(root, sum);
}

Fifth: Test It in main() #

Now you can easily check for path sums from your main function. For example, to check if a path sum of 27 exists:

cout << "Check if path sum 27 exists: " << (tree.hasPathSum(27) ? "Yes" : "No") << endl;

Full Modified main.cpp Snippet #

#include <iostream>
#include "BinaryTree.h"
#include "TreeNode.h"
using namespace std;

int main() {
    BinaryTree tree;
    tree.add(5);
    tree.add(6);
    tree.add(3);
    tree.add(4);
    tree.add(9);
    tree.add(11);
    // Add the 7 node if you want to test the 5-4-11-7 path sum of 27
    // tree.add(7);

    cout << "Height of the tree is: " << tree.height() << "\n";
    cout << "In Order Show:" << endl;
    tree.inorderShow();
    cout << "\nCheck if path sum 27 exists: " << (tree.hasPathSum(27) ? "Yes" : "No") << endl;

    system("pause");
    return 0;
}

Key Notes #

• The recursive function works by "carrying over" the remaining sum we need to reach as we traverse down the tree.
• The overloaded hasPathSum(int sum) hides the internal TreeNode* details from the caller, which is good encapsulation practice.
• We use 1 and 0 as return values since the function prototype specifies int (matching C-style boolean returns).

内容的提问来源于stack exchange，提问作者Vytautas