15 道二叉树手写算法题（二）
在上一期讲到，树和链表的手写算法题在面试中出现的频率最高。也正是因为这样，如果你马上就要参加面试，但之前没有刷多少算法题，那么很建议你先看看树和链表相关的题目。而且树和链表的算法题学习难度相比于其它内容低很多，所以面试前学习这些知识性价比很高。
4. 判断是否存在和等于一个数的路径
Leetcdoe : 112. Path Sum (Easy)
对于上面的一棵树，题目要求的目标和为 5。该树存在一个 0 -> 1 -> 4 的路径，这个路径的和为 5，因此返回 true。
使用递归的思路求解：对于一棵树，其根节点为 root，如果两颗子树任意一颗存在和为 sum - root.val，那么再加上根加点 root.val，总和为 sum。在两颗子树上的求解可以继续使用该递归函数。
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
if (root.left == null && root.right == null && root.val == sum) return true;
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}5. 统计路径和等于一个数的路径数量
Leetcode : 437. Path Sum III (Easy)
这题要找的路径不再需要从根节点到叶子节点，只需要连续即可。对于上面的树，题目要求的目标和为 2，该树存在 5 个和为 2 的路径：
很容易找到以根节点为起点的一个路径，不过本题没有限制要以根节点为起点。但是可以稍作转换，将问题转换为：以根节点为起点，和不以根节点为起点。对于求解函数 pathSum，无法直接使用该函数实现以根节点为起点的求解，因此新定义一个函数 pathSumStartWithRoot。不以根节点为起点的求解可以对两颗子树使用 pathSum，因为子树不包含根节点。
public int pathSum(TreeNode root, int sum) {
if (root == null) return 0;
int ret = pathSumStartWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
return ret;
}
private int pathSumStartWithRoot(TreeNode root, int sum) {
if (root == null) return 0;
int ret = 0;
if (root.val == sum) ret++;
ret += pathSumStartWithRoot(root.left, sum - root.val) + pathSumStartWithRoot(root.right, sum - root.val);
return ret;
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-04-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录