首页 > 代码库 > LeetCode:Path Sum
LeetCode:Path Sum
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.
解题思路:
由于需要找寻根到叶子节点的路径和,我们可以通过遍历一颗树即可得知,通常树的遍历有
四种方式:先序遍历、中序遍历、后序遍历、层次遍历,任选一种遍历方式即可.
解题代码(非递归):
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool hasPathSum(TreeNode *root, int sum) { if(!root) return false; queue<pair<TreeNode *,long long> > que; que.push(make_pair(root,root->val)); while(!que.empty()) { pair<TreeNode *,long long> p = que.front(); que.pop(); if(p.first->left == NULL && p.first->right == NULL && p.second == sum) return true; if(p.first->left) que.push(make_pair(p.first->left,p.second + p.first->left->val)); if(p.first->right) que.push(make_pair(p.first->right,p.second + p.first->right->val)); } return false; } };
解题代码(递归解):
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool dfs(TreeNode *rt,long long sum) { if (rt->left == rt->right && !rt->left) return sum == rt->val ; if (rt->left && rt->right) return dfs(rt->left,sum - rt->val) | dfs(rt->right,sum - rt->val); return dfs(rt->left ? rt->left : rt->right, sum - rt->val); } bool hasPathSum(TreeNode *root, int sum) { return root ? dfs(root,sum) : false ; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。