题目:给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。
示例 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] 内
思路:化为子问题寻找根的左子树和右子树的最小深度;结束条件为空、叶子节点;
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;
}
题目:给你二叉树的根节点 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] 内
思路:化为子问题将 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);
}