C++ 二叉树寻路

Question

我有一个关于求二叉整型树路径之和的问题。这是针对大学的，因此要求如下：从 Lab Sheet 3B (Binary Tree) 中获取整数二叉树的代码，并编写一个名为 hasPathSum() 的方法给出了一个二叉树和一个总和，return 如果树为真有一条 root-to-leaf 路径，使得沿路径的所有值相加等于给定和。 Return 如果找不到这样的路径，则返回 false。函数原型为

int hasPathSum(struct node* node, int sum)

注意："root-to-leaf path"是树中从根节点开始的一系列节点并向下进行到叶子（没有 children 的节点）。一棵空树包含没有 root-to-leaf 路径。因此，例如，下面的树正好有四个 root-to-leaf 路径：

5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
Root-to-leaf paths:
path 1: 5 4 11 7
path 2: 5 4 11 2
path 3: 5 8 13
path 4: 5 8 4 1

对于这个问题，我们将关注这样一条路径的值的总和——对于例如，5-4-11-7 路径上的值之和为 5 + 4 + 11 + 7 = 27.

我遇到了麻烦。我有一个二叉树，但是函数 hasPathSum() 需要传递一个节点，而不是树。我不知道该怎么做。我也不知道如何找到从根到叶的路径总和（还有 hasPathSum 主体）。这需要递归完成。

非常感谢任何帮助。

这是我的节点class:

#include <stdio.h>
#pragma once
struct TreeNode
{
public:
    friend class BinaryTree;
    TreeNode(int theData) : data(theData) {}
    bool isLeaf();
private:
    int data;
    TreeNode *leftlink;
    TreeNode *rightLink;
};

这是 BinaryTree 头文件：

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

#pragma once
class BinaryTree
{
public:
    BinaryTree();
    void add(int toadd);
    int height();
    void inorderShow() const;
    int hasPathSum(TreeNode * tree, int sum);
private:
    void add(TreeNode *toAdd, TreeNode *& addHere);
    int height(TreeNode *& root);
    TreeNode *root;
    void inorderShow(TreeNode *subTree) const;
};

还有我的 BinaryTree cpp 文件：

#include "BinaryTree.h"

BinaryTree::BinaryTree()
{
}

void BinaryTree::add(int toAdd)
{
    TreeNode *node = new TreeNode(toAdd);
    add(node, root);
}

int BinaryTree::height()
{
    return height(root);
}

void BinaryTree::add(TreeNode * toAdd, TreeNode *& addHere)
{
    if (addHere == NULL)
        addHere = toAdd;
    else if (toAdd->data < addHere->data)
        add(toAdd, addHere->leftlink);
    else //toAdd->data >= addHere->data
        add(toAdd, addHere->rightLink);
}

int BinaryTree::height(TreeNode *& n)
{
    if (n == NULL)
        return -1;
    else
        return 1 + max(height(n->leftlink), height(n->rightLink));
}

void BinaryTree::inorderShow(TreeNode * subTree) const
{
    if (subTree != NULL)
    {
        inorderShow(subTree->leftlink);
        cout << subTree->data << " ";
        inorderShow(subTree->rightLink);
    }
}

void BinaryTree::inorderShow() const
{
    inorderShow(root);
}

int BinaryTree::hasPathSum(TreeNode * tree, int sum)
{

}

在main.cpp中，我有一棵树如下：

#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);
    cout << "Height of the tree is: ";
    cout << tree.height() << " ";

    cout << "\nIn Order Show:" << endl;
    tree.inorderShow();

    cout << "Root to leaft path: " << endl;

    cout << endl;
    system("pause");
    return 0;
}

是否有人可以解释我如何完成此任务并满足要求（也就是不更改函数 hasPathSum() 参数），我将不胜感激。

Answer 1

在我看来要求是错误的（或者可能是混淆的）

and code a method called hasPathSum() which given a binary tree and a sum

鉴于这是二叉树的一种方法 class 树是隐式传递的，因此唯一显式参数是总和。所以该方法应该声明为

class BinaryTree
{
    ...
    bool hasPathSum(int sum);
    ...
};

但是给定的签名是

int hasPathSum(struct node* node, int sum)

有错误的 return 类型（int 而不是 bool）和无法解释的 node 参数。

下面是我将如何组织解决方案，因为它涉及两种方法，它可能解释了混乱。

class BinaryTree
{
    ...
public:
    bool hasPathSum(int sum) { return hasPathSumHelper(root, sum); }
    ...
private:
    static bool hasPathSumHelper(TreeNode* node, int sum);
};

public hasPathSum 方法具有问题描述所隐含的签名（唯一有意义的签名）。它只是调用一个私有方法 hasPathSumHelper 传递根节点和总和，这解决了如何传递私有根节点的问题。

hasPathSumHelper 方法是真正工作完成的递归例程（留给您实施）。 public hasPathSum 只是通过调用此方法开始计算。

当您考虑如何实现 hasPathSumHelper 时，您可能会发现添加额外的参数很有用（一个 sum_so_far 参数，随着树的下降，它是所有节点的总和以上你对我来说很有意义）。没关系，因为它是一个私有方法，你可以添加你喜欢的。

C++ 二叉树寻路

C++ Binary Tree Path finding

c++

tree

binary-tree

binary-search-tree