112. 路径总和

递归

  1. class Solution {
  2. public:
  3.     bool hasPathSum(TreeNode* root, int targetSum) {
  4.         if(root==NULL)return false;
  5.         sum +=root->val;
  6.         if(!root->left&&!root->right)
  7.         {
  8.             if(sum==targetSum)return true;
  9.             else return false;
  10.         }
  11.         if(root->left)
  12.             if(hasPathSum(root->left,targetSum))return true;
  13.         //回溯
  14.             else sum -=root->left->val;
  15.         if(root->right)
  16.             if(hasPathSum(root->right,targetSum))return true;
  17.             else sum -=root->right->val;
  18.         return false;
  19.     }
  20.     int sum = 0;
  21. };
 class Solution {
public:
    bool dfs(TreeNode* Node,int count)
    {
        if(!Node->left && !Node->right)
        {
            if(count==0)return true;
            else return false;
        }
        if(Node->left)
            if(dfs(Node->left,count-Node->left->val))return true;
        if(Node->right)
            if(dfs(Node->right,count-Node->right->val))return true;
        return false;

    }
    bool hasPathSum(TreeNode* root, int targetSum) {
       if(root==NULL)return false;
       return dfs( root,targetSum-root->val);
    }
};