c++ concise dfs solution.


  • 0
    class Solution {
    public:
      bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL)
        {
          return false;
        }
        vector<int> nums;
        dfs(root, nums, 0);
        for (auto i : nums)
        {
          if (sum == i)
          {
            return true;
          }
        }
        return false;
      }
      void dfs(TreeNode *root, vector<int> &nums, int num)
      {
        num = num + root -> val;
        if (root -> left != NULL)
        {
          dfs(root -> left, nums, num);
        }
        if (root -> right != NULL)
        {
          dfs(root -> right, nums, num);
        }
        if (root -> left == NULL && root -> right == NULL)
        {
          nums.push_back(num);
        }
      }
    };
    

  • 0
    C

    This might be suitable for Path Sum II, but backtracking here is overkilling. Returning when it reaches the first occurrence makes a little more sense.

    void pathHelper(TreeNode *root, bool &flag, int &ret, int &sum) {
        if (!root || flag) return;
        ret += root->val;
        if (!root->left && !root->right) flag = ret == sum;
        pathHelper(root->left, flag, ret, sum);
        pathHelper(root->right, flag, ret, sum);
        ret -= root->val;
    }
    
    bool hasPathSum(TreeNode* root, int sum) {
        int ret{};
        bool flag{};
        pathHelper(root, flag, ret, sum);
        return flag;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.