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 1return true, as there exist a root-to-leaf path 5-4-11-2 which sum is 22.
Submit your solution : https://leetcode.com/problems/path-sum/
Recursion
Recursively, if we visit a leaf node, we check the remaining sum with the value of the node. We subtract the value of nodes from the intended sum and carry them recursively down along the leaf nodes from the root.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | /** * 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)) { // if it is a leaf node, we compare the remaining sum with the value return sum == root->val; } // subtract the node value and continue visit two sub trees. return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val); } }; |
/**
* 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)) {
// if it is a leaf node, we compare the remaining sum with the value
return sum == root->val;
}
// subtract the node value and continue visit two sub trees.
return hasPathSum(root->left, sum - root->val) ||
hasPathSum(root->right, sum - root->val);
}
};This recursion is a DFS (Depth First Search) meaning that it may be quicker to find a route. For example, if the first route satisfies, the program will exit very soon without exploring the full search tree.
Iterative
The BFS (Breadth First Search) uses a queue data structure to store the current parent node. Every iteration, the queue pops out a front node and pushes back its children, this eventually gives a level-by-level traversal. It means, that it is likely for the BFS to explore full every possible nodes in the search tree.
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 | class Solution { public: bool hasPathSum(TreeNode* root, int sum) { if (root == NULL) { return false; } queue< pair<TreeNode*, int> > q; q.push(make_pair(root, sum)); // we have to add up to sum while (!q.empty()) { auto p = q.front(); // get front element from the queue q.pop(); if (p.first->left != NULL) { // pushes left q.push(make_pair(p.first->left, p.second - p.first->val)); } if (p.first->right != NULL) { // pushes right q.push(make_pair(p.first->right, p.second - p.first->val)); } if ((p.first->left == NULL) && (p.first->right == NULL)) { if (p.second == p.first->val) { // if it is a leaf node and the sum adds up. return true; } } } return false; // finish the tree, but no routes found. } }; |
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == NULL) {
return false;
}
queue< pair<TreeNode*, int> > q;
q.push(make_pair(root, sum)); // we have to add up to sum
while (!q.empty()) {
auto p = q.front(); // get front element from the queue
q.pop();
if (p.first->left != NULL) { // pushes left
q.push(make_pair(p.first->left, p.second - p.first->val));
}
if (p.first->right != NULL) { // pushes right
q.push(make_pair(p.first->right, p.second - p.first->val));
}
if ((p.first->left == NULL) && (p.first->right == NULL)) {
if (p.second == p.first->val) { // if it is a leaf node and the sum adds up.
return true;
}
}
}
return false; // finish the tree, but no routes found.
}
};–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How to Convert Roman to Integer in C/C++ and Python?
Next Post: How to Do Binary Tree Inorder Traversal in C/C++?
