神刀安全网

C/C++ Coding Exercise – Path Sum for Binary Tree

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.

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.

/**  * 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.

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–

GD Star Rating

loading…

484 words

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » C/C++ Coding Exercise – Path Sum for Binary Tree

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮