# LeetCode Easy 112. Path Sum

tags: leetcode

問題

• Explore
• Problems

アイデア

与えられた木の根から葉までのたどる際に，与えられた値となるような経路はあるかという問題です．

解法

与えられた値にノードの値の合計がなるということは，与えられた値からノードの値を引いて$0$になるかどうかを調べれば良いです．

• 根がないときはfalseを返します
• 根があるときは与えられた関数を以下のように再帰的に実行します
  • 左右子がない
    • 現在のノードの値が合計と一致するかどうかを返します
  • 左右子がある
    • 現在のノードの値を合計から引き，左右子から再帰的に関数を実行する
  • 左子がある
    • 現在のノードの値を合計から引き，左子から再帰的に関数を実行する
  • 右子がある
    • 現在のノードの値を合計から引き，右子から再帰的に関数を実行する

計算量

ノードの数を$N$とします

• 時間計算量
  • $O(N)$
• 空間計算量
  • 再帰関数の深さは木の深さに依存します
  • 木の深さは平均で$O(\log N)$で最悪$O(N)$であり，それが空間計算量です

C++

/**
 * 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)
      return false;
    int curVal = root->val;
    auto left = root->left, right = root->right;
    
    if (!left && !right)
      return (curVal == sum);
    else if (left && right)
      return hasPathSum(left, sum - curVal) || hasPathSum(right, sum - curVal);
    else if (left)
      return hasPathSum(left, sum - curVal);
    else // right
      return hasPathSum(right, sum - curVal);
  }
};