Leetcode 112. Path Sum (C語言)

• 題目
  Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
  Note: A leaf is a node with no children.
• 範例

Example:

Given the below binary tree and sum = 22,

​      5
​     / \
​    4   8
​   /   / \
​  11  13  4
​ /  \      \
7    2      1

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

思路:空樹回傳0,左右子點為空代表只有自己是leaf,看sum扣掉是否為0回傳1,否則表示有子樹。

1. 如果左子樹為空，右子樹往下找
2. 如果右子樹為空，左子樹往下找
3. 左右子樹皆不為空，左右子樹皆往下找,回傳值做or。