作者:
晚于: 2020-08-05 12:00:00后提交分数乘系数50%
截止日期: 2020-08-12 12:00:00
问题描述 :
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/
4 8
/ /
11 13 4
/
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
可使用以下main函数：
#include <iostream>
#include <queue>
#include <cstdlib>
#include <cstring>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(NULL), right(NULL) {}
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
TreeNode* inputTree()
{
int n,count=0;
char item[100];
cin>>n;
if (n==0)
return NULL;
cin>>item;
TreeNode* root = new TreeNode(atoi(item));
count++;
queue<TreeNode*> nodeQueue;
nodeQueue.push(root);
while (count<n)
{
TreeNode* node = nodeQueue.front();
nodeQueue.pop();
cin>>item;
count++;
if (strcmp(item,"null")!=0)
{
int leftNumber = atoi(item);
node->left = new TreeNode(leftNumber);
nodeQueue.push(node->left);
}
if (count==n)
break;
cin>>item;
count++;
if (strcmp(item,"null")!=0)
{
int rightNumber = atoi(item);
node->right = new TreeNode(rightNumber);
nodeQueue.push(node->right);
}
}
return root;
}
int main()
{
TreeNode* root;
root=inputTree();
int sum;
cin>>sum;
bool res=Solution().hasPathSum(root,sum);
cout<<(res?"true":"false");
}
输入说明 :
首先输入结点的数目n（注意，这里的结点包括题中的null空结点）
然后输入n个结点的数据，需要填充为空的结点，输入null。
最后输入一个整数sum。
输出说明 :
输出true或false
输入范例 :
输出范例 :
#include <iostream> #include <queue> #include <cstdlib> #include <cstring> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(NULL), right(NULL) {} TreeNode(int x) : val(x), left(NULL), right(NULL) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; class Solution { public: bool hasPathSum(TreeNode* root, int sum) { if(root==NULL) return false; if(root->left==NULL&&root->right==NULL) return sum-root->val==0; return hasPathSum(root->left, sum - root->val)|| hasPathSum(root->right, sum - root->val); } }; TreeNode* inputTree() { int n,count=0; char item[100]; cin>>n; if (n==0) return NULL; cin>>item; TreeNode* root = new TreeNode(atoi(item)); count++; queue<TreeNode*> nodeQueue; nodeQueue.push(root); while (count<n) { TreeNode* node = nodeQueue.front(); nodeQueue.pop(); cin>>item; count++; if (strcmp(item,"null")!=0) { int leftNumber = atoi(item); node->left = new TreeNode(leftNumber); nodeQueue.push(node->left); } if (count==n) break; cin>>item; count++; if (strcmp(item,"null")!=0) { int rightNumber = atoi(item); node->right = new TreeNode(rightNumber); nodeQueue.push(node->right); } } return root; } int main() { TreeNode* root; root=inputTree(); int sum; cin>>sum; bool res=Solution().hasPathSum(root,sum); cout<<(res?"true":"false"); }