【Leetcode -111.二叉树的最小深度 -112.路径总和】
【Leetcode -111.二叉树的最小深度 -112.路径总和】
Leetcode -111.二叉树的最小深度
题目：给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3, 9, 20, null, null, 15, 7] 输出：2
示例 2： 输入：root = [2, null, 3, null, 4, null, 5, null, 6] 输出：5
提示： 树中节点数的范围在[0, 10^5] 内
- 1000 <= Node.val <= 1000
思路：化为子问题寻找根的左子树和右子树的最小深度；结束条件为空、叶子节点；
int minDepth(struct TreeNode* root)
{
if (root == NULL)
return 0;
//叶子返回 1
if (root->left == NULL && root->right == NULL)
return 1;
//当前根的左子树为空，就去递归右子树的深度
if (root->left == NULL)
return minDepth(root->right) + 1;
//当前根的右子树为空，就去递归左子树的深度
if (root->right == NULL)
return minDepth(root->left) + 1;
//记录左子树和右子树的深度，最后返回深度小的
int LeftDepth = minDepth(root->left) + 1;
int RightDepth = minDepth(root->right) + 1;
return LeftDepth > RightDepth ? RightDepth : LeftDepth;
}Leetcode -112.路径总和
题目：给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。 如果存在，返回 true ；否则，返回 false 。 叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1, 2, 3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 – > 2) : 和为 3 (1 – > 3) : 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。
示例 3： 输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
提示： 树中节点的数目在范围[0, 5000] 内
- 1000 <= Node.val <= 1000
- 1000 <= targetSum <= 1000
思路：化为子问题将 targetSum 减去当前根的 val ，作为下一个函数递归的新的 targetSum ，判断它的左子树或者右子树的路径总和是否等于新的 targetSum；结束条件为空、只剩一个节点；
bool hasPathSum(struct TreeNode* root, int targetSum)
{
//空树返回false
if (root == NULL)
return false;
//只剩一个节点，判断当前 targetSum 是否等于当前根的 val
if (root->left == NULL && root->right == NULL)
return targetSum == root->val;
//递归当前根的左子树和右子树，新的 targetSum 等于原来的 targetSum 减去当前根的 val，作为下一个函数的参数
return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}腾讯云开发者
