minimum-depth-of-binary-tree & path-sum

题目描述

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

题解

注意只有一棵子树的情况。

int minDepth(TreeNode* root) {
	if (!root)return 0;
	if (!root->right && !root->left)return 1;
	if (!root->left)return 1 + minDepth(root->right);
	if(!root->right)return 1 + minDepth(root->left);
	return 1 + min(minDepth(root->left), minDepth(root->right));
}

题目描述

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

题解

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