Инициализация бинарного дерева для использования в функции

Question

У меня есть объявленная структура:

struct TreeNode
{
    int val;
    TreeNode* left, *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

Также у меня есть функция, которую надо затестить

bool hasPathSum(TreeNode* root, int targetSum) // Does Tree has pathsum?
    {
        if (!root) return false;

        if (!root->left && !root->right && root->val == targetSum)
        {
            return true;
        }

        if (root->left)
        {
            hasPathSum(root->left, targetSum - root->val);
        }

        if (root->right)
        {
            hasPathSum(root->right, targetSum - root->val);
        }

        return false;
    };

Я хочу вызвать функцию hasPathSum в main, но я не знаю, как правильно создать дерево с определёнными листьями, чтобы я мог отправить его в функцию. Например, я хочу проверить, как моя функция отработает с деревом [1,2,3]. Что нужно написать?

Я знаю, что вопрос очень простой, но я никак не могу додуматься до ответа.

Answer 1

Ну во-первых, ваша функция hasPathSum() всегда будет возвращать false для любого дерева, число узлов которого больше единицы. Присмотритесь внимательно.

Во-вторых, при рекурсивном вызове hasPathSum() параметр root гарантированно не может быть равен nullptr, т.к. это проверяется перед вызовом. Следовательно, проверять root на нулевое значение в каждой рекурсии не имеет смысла. Целесообразно разделить эту функцию на две части. Первая - собственно сама функция hasPathSum(), не рекурсивная, содержащая проверку root на nullptr - один раз:

bool hasPathSum(TreeNode* root, int targetSum) // Does Tree has pathsum?
{
    if (root) return hasPathSum_recursive(root, targetSum);
    return false;
}

и вторая часть - рекурсивная (привожу исправленный вариант):

bool hasPathSum_recursive(TreeNode* root, int targetSum)
{
    //It's guaranteed the root is not NULL

    if (root->left)
    {
        if (hasPathSum_recursive(root->left, targetSum - root->val)) return true;
    }

    if (root->right)
    {
        return hasPathSum_recursive(root->right, targetSum - root->val);
    }

    if (root->val == targetSum) return true;
    return false;
};

Теперь по тестированию. Проще всего создать тестовое дерево динамически. Например так:

/*
    Creating the following tree (for testing):
             1
            / \
           2   3
          / \
         5   7
            / \
               4
*/

#define T(val,left,right) new TreeNode(val,left,right)
TreeNode* pTestRoot = 
    T(1,
        T(2,
            T(5,
                nullptr,
                nullptr
            ),
            T(7,
                nullptr,
                T(4,
                    nullptr,
                    nullptr
                )
            )
        ),
        T(3,
            nullptr,
            nullptr
        )
    );
#undef T

В конце программы, соответственно, надо не забыть удалить дерево из памяти, вызвав функцию:

void delTree(TreeNode* root)
{
    if (root)
    {
        delTree(root->left);
        delTree(root->right);
        delete root;
    }
}

Ну и подытожим полным текстом программы:

#include <stdio.h>

struct TreeNode
{
    int val;
    TreeNode* left, *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};


bool hasPathSum_recursive(TreeNode* root, int targetSum)
{
    //It's guaranteed the root is not NULL

    if (root->left)
    {
        if (hasPathSum_recursive(root->left, targetSum - root->val)) return true;
    }

    if (root->right)
    {
        return hasPathSum_recursive(root->right, targetSum - root->val);
    }

    if (root->val == targetSum) return true;
    return false;
};

bool hasPathSum(TreeNode* root, int targetSum) // Does Tree has pathsum?
{
    if (root) return hasPathSum_recursive(root, targetSum);
    return false;
}


void delTree(TreeNode* root)
{
    if (root)
    {
        delTree(root->left);
        delTree(root->right);
        delete root;
    }
}


const char* boolStr(bool bVal)
{
    static const char szTrue[] = "true";
    static const char szFalse[] = "false";

    if (bVal) return szTrue;
    return szFalse;
}

void test_print(TreeNode* pTestRoot, int targetSum)
{
    printf("targetSum == %2d,  hasPathSum(&testRoot, targetSum) == %s\n", targetSum, boolStr(hasPathSum(pTestRoot, targetSum)));
}


int main()
{
    /*
        Creating the following tree (for testing):
                 1
                / \
               2   3
              / \
             5   7
                / \
                   4
    */

    #define T(val,left,right) new TreeNode(val,left,right)
    TreeNode* pTestRoot = 
        T(1,
            T(2,
                T(5,
                    nullptr,
                    nullptr
                ),
                T(7,
                    nullptr,
                    T(4,
                        nullptr,
                        nullptr
                    )
                )
            ),
            T(3,
                nullptr,
                nullptr
            )
        );
    #undef T

    //testing it
    test_print(pTestRoot, 8);
    test_print(pTestRoot, 19);
    test_print(pTestRoot, 14);
    test_print(pTestRoot, 27);
    test_print(pTestRoot, 4);
    test_print(pTestRoot, 5);

    //delete the tree
    delTree(pTestRoot);

    return 0;
}

Будет выведено:

targetSum ==  8,  hasPathSum(&testRoot, targetSum) == true
targetSum == 19,  hasPathSum(&testRoot, targetSum) == false
targetSum == 14,  hasPathSum(&testRoot, targetSum) == true
targetSum == 27,  hasPathSum(&testRoot, targetSum) == false
targetSum ==  4,  hasPathSum(&testRoot, targetSum) == true
targetSum ==  5,  hasPathSum(&testRoot, targetSum) == false

БЛОГ НА HUSL

Инициализация бинарного дерева для использования в функции

Ответы (1 шт):