# Leetcode 112：路径总和

## 示例

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

## 代码实现

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

# Leetcode 113：路径总和II

## 示例

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

[
[5,4,11,2],
[5,8,4,5]
]

## 代码实现

void hasPathSum(TreeNode* root, int sum, vector<vector<int>>& result, vector<int>& temp) { sum -= root->val; temp.push_back(root->val); if (sum == 0 && (root->left == nullptr) && (root->right == nullptr)) { result.push_back(temp); return; } if (root->left) { hasPathSum(root->left, sum, result, temp); temp.pop_back(); } if (root->right) { hasPathSum(root->right, sum, result, temp); temp.pop_back(); }}vector<vector<int>> pathSum(TreeNode* root, int sum) { vector<vector<int>>result; if (root == nullptr) return result; vector<int>temp; hasPathSum(root, sum, result, temp); return result;}

# Leetcode 437：路径总和III

## 示例

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

 10 / \5 -3

/ \ \
3 2 11
/ \ \
3 -2 1

1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11

## 代码实现

int psum(TreeNode* root, int sum){ if (root == nullptr) return 0; int res = 0; if (root->val == sum) res += 1; res += psum(root->left, sum - root->val); res += psum(root->right, sum - root->val); return res;}int pathSum(TreeNode* root, int sum) { if (root == nullptr) return 0; return psum(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);}

O(n)，n为树的节点个数；

O(h)，h为树的高度；