首页 > 代码库 > Path Sum

Path Sum

2024-07-17 23:17:12   228人阅读

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 class Solution {2 public:3     bool hasPathSum( TreeNode *root, int sum ) {4         if( !root ) { return false; }5         if( !root->left && !root->right ) { return root->val == sum; }6         return hasPathSum( root->left, sum - root->val ) || hasPathSum( root->right, sum - root->val );7     }8 };

 


联系
我们