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 == nullreturn 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 == nullreturn 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 == nullreturn 0;
    int ret = 0;
    if (root.val == sum) ret++;
    ret += pathSumStartWithRoot(root.left, sum – root.val) + pathSumStartWithRoot(root.right, sum – root.val);
    return ret;
}
本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 15 道二叉树手写算法题(二)

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多