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); }
