Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
Hide Tags :Tree, Depth-first Search
题目:找出二叉树中是否有从根节点到树叶路径的值之和等于给定的数据sum
思路:凡是设计到二叉树的查找,搜索…採用递归是一种较好的方法。
1、给出递归终止条件,也就是
A:当节点为NULL时返回false
B:当节点为树叶(无儿子节点)时,检查此树叶的val是否与sum相等,相等则返回true。否则返回false
2、当不是终止条件B时。继续向下递归。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */bool hasPathSum(struct TreeNode* root, int sum) { if(root == NULL) return false; if(root->left == NULL && root->right == NULL) return sum == root->val; return (hasPathSum(root->left,sum - root->val) || hasPathSum(root->right,sum - root->val));
一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!
二、互相尊重,对自己的言论和行为负责。