[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. rootNULL 時(意味 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);
}
Show Comments