112. path sum

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,
1
2
3
4
5
6
7
      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.

题意分析：
注意必须是叶子节点的时候才计算是否和sum相等。

class Solution {
public:
    bool (TreeNode *node,int sumVal,int sum)
    {
        if (node == NULL)
            return false;
        
        if (node->left == NULL && node->right == NULL)
            return sumVal + node->val == sum;
            
        return dfs(node->left,sumVal + node->val ,sum) || dfs(node->right,sumVal + node->val,sum);
    }
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL)
            return false;
            
        return dfs(root,0,sum);
    }
};

112. path sum

近期文章

近期评论

标签

热门

文章归档

分类目录

功能