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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
递归方法： /** * Definition for a binary tree node. * 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 == NULL) return false; if(root->left == NULL && root->right == NULL && sum == root->val) return true; if(hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val)) return true; else return false; } }; 非递归法 /** * Definition for a binary tree node. * 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) { queue<TreeNode *> q; if(root == NULL) return false; q.push(root); TreeNode *temp; while(!q.empty()) { int size = q.size(); while(size--) { temp = q.front(); q.pop(); if(temp->left != NULL) { q.push(temp->left); temp->left->val += temp->val; } if(temp->right != NULL) { q.push(temp->right); temp->right->val += temp->val; } if(temp->left == NULL && temp->right == NULL && (temp->val == sum || temp->val == sum)) { return true; } } } return false; } }; |
❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼
❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼
❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版
