【牛客刷题 - 算法】NC9 二叉树中和为某一值的路径 (一)

作者：清风莫追

2022 年 10 月 03 日
湖南
本文字数：1071 字
阅读完需：约 4 分钟

个人主页：清风莫追
系列专栏：牛客刷题——数据结构与算法推荐一款面试、刷题神器牛客网：👉点击开始刷题学习👈

@[toc]

1.题目描述

描述给定一个二叉树 root 和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
叶子节点是指没有子节点的节点
路径只能从父节点到子节点，不能从子节点到父节点
总节点数目为 n

例如：给出如下的二叉树， $s u m = 22$

返回 true，因为存在一条路径 $5 \to 4 \to 11 \to 2$ 的节点值之和为 22。

数据范围：1.树上的节点数满足 $0 \leq n \leq 10000$ 2.每个节点的值都满足 $∣ v a l ∣ \leq 1000$ 要求：空间复杂度 $O (n) O (n)$ ，时间复杂度 $O (n) O (n)$ 进阶：空间复杂度 $O (树的高度) O (树的高度)$ ，时间复杂度 $O (n) O (n)$

2.算法设计思路

核心其实就是一个二叉树的遍历。可以采用回溯法，在遍历树的过程中，利用一个全局变量num记录遍历到当前节点时路径上所有值的和。

当以当前结点为根的子二叉树中没有符合要求的叶子结点时，就向上回溯（从父结点到子结点时，num的值增加了；因此返回时就减去相应的值。）

3.代码实现

注：这里并不是完整代码，而只是核心代码的模式

/** * struct TreeNode { *  int val; *  struct TreeNode *left; *  struct TreeNode *right; * }; *//** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * *  * @param root TreeNode类  * @param sum int整型  * @return bool布尔型 */int num = 0;
bool hasPathSum(struct TreeNode* root, int sum ) {    // write code here    bool flag = false;
    if(root == NULL){return false;}    num += root->val;    //printf("num:%d\n", num);    if(num == sum && root->left == NULL && root->right == NULL){return true;}
    //查找左右子树    if(hasPathSum(root->left, sum) == true){return true;}    else {flag = true;}    if(hasPathSum(root->right, sum) == true){return true;}    else {flag = true;}
    //回溯    if(flag == true){        num -= root->val;        return false;    }        //最后不加个返回，就会显示编译错误。其实前面逻辑上是一定会有返回值的    printf("error\n");    return false;}