专栏首页Java那些事15 道二叉树手写算法题(二)

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

本文分享自微信公众号 - 程序员乔戈里(CXYqiaogeli),作者:CyC2018

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每天一道剑指offer-二叉树的镜像

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

    乔戈里
  • 每天一道剑指offer-二叉树的深度

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

    乔戈里
  • 每天一道leetcode88-合并两个有序数组

    乔戈里
  • 剑指Offer - 面试题54. 二叉搜索树的第k大节点(二叉树循环遍历)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kd...

    Michael阿明
  • python中创建和遍历二叉树

    py3study
  • 每天一道剑指offer-二叉树的镜像

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

    乔戈里
  • Golang Leetcode 450. Delete Node in a BST.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89175007

    anakinsun
  • 利用rbd命令把 ceph pool 中的一个镜像导出

    查看镜像 [root@node1 ~]# rbd ls images a56330e7-79d7-4639-a68f-366ac344bfe2 eccfee07...

    院长技术
  • 浏览器环境检测

    本文是直接把seleniumpyppeteer 以及正常打开浏览器 的环境差异直接列出来

    爬虫
  • 如何使用CP / SCP / RSYNC在Linux中排除特定目录?

    对于任何系统管理员或一般Linux操作系统用户而言,在服务器之间执行文件复制操作都是一项常见任务。在将文件从一个系统复制到另一个系统时,由于某些特定原因,我们可...

    用户6543014

扫码关注云+社区

领取腾讯云代金券