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; queueque; que.push(make_pair(root,root->val)); while(!que.empty()) { pair 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 ; } };