[LeetCode 解題筆記] Path Sum

LeetCode 原題目網址：112. Path Sum

題目描述

給定一棵 Binary Tree 的 root 以及 targetSum ，如果這棵 Binary Tree 存在一條從 root 到 leaf 的 path，將 path 上所有 nodes 的 value 相加等於 targetSum 的話，就 return true ，否則 return false 。

題目其中有一個限制，Binary Tree 有可能為空。

解題思路

這一題可以用簡單的遞迴解決。

Base case 有兩個：

1. 當 root 為 NULL 時（意味 Binary Tree 為空），直接 return false 。
2. Binary Tree 只有一個 node 時（意味 root 其左子點跟右子點為 NULL），則看 root node 的 value 是否等於 targetSum 。

下面為用 C 語言實作的程式碼：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


bool hasPathSum(struct TreeNode* root, int targetSum){
  if (!root) {
    return false;   
  }
  if (root->left == NULL && root->right == NULL) {
    return root->val == targetSum;
  }
    
  return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}