NC9 二叉树中是否存在节点和为指定值的路径

vlambda
2021-07-21

NC9 二叉树中是否存在节点和为指定值的路径

情景提要

牛客题解系列，按照题号顺序开始。

NC9 二叉树中是否存在节点和为指定值的路径

题目描述

输入输出示例

输入:

{1,2} 0

输出:

false

题目分析

思路

本题和NC5,NC9 是相似的，依然是递归和迭代两种方法都可以做，只需要改变一下计算和的方式就可以了。本题是将每个节点的值加起来，之前的题是将节点上的数字组成一个新的数。本题是返回bool类型，表示是否存在。之前的题是返回数组，表示具体的路径。这就是和之前两道题的小区别。

代码实现

方法

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
class Solution {public: /** *  * @param root TreeNode类  * @param sum int整型  * @return bool布尔型 */ bool hasPathSum(TreeNode* root, int sum) { // write code here if(!root) return false; return travel(root,sum); } bool travel(TreeNode* node,int sum){ if(!node->left && !node->right) { if(node->val == sum) return true; return false; } bool l = false; bool r = false; if(node->left) { node->left->val += node->val; l = travel(node->left, sum); } if(node->right) { node->right->val += node->val; r = travel(node->right, sum); } return l || r; }};