Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

路径总和-112 #57

Open
sl1673495 opened this issue Jun 6, 2020 · 0 comments
Open

路径总和-112 #57

sl1673495 opened this issue Jun 6, 2020 · 0 comments
Labels
DFS 深度优先遍历 二叉树 例题详解 每个分类下会挑出几道题目进行精讲,其他的同类题目会默认拥有这些前置知识而简略讲解。 待复习 看题解或者做出来很艰难的,需要回顾。

Comments

@sl1673495
Copy link
Owner

sl1673495 commented Jun 6, 2020

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

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

示例:

给定如下二叉树,以及目标和 sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

思路

从第一个节点求是否有路径之和为 22,可以转化为从左节点开始,是否有路径之和为 22 -5 = 18,也可以转化为从右节点开始,是否有路径之和为 22 - 5 = 18。

当递归调用函数时,发现节点没有左右子节点,说明它是叶子节点,此时就可以对比当前的值是否和传入的目标值 sum 相等,返回结果即可。

let hasPathSum = function (root, sum) {
  if (!root) {
    return false
  }
  // 叶子节点 判断当前的值是否等于 sum 即可
  if (!root.left && !root.right) {
    return root.val === sum
  }

  return (
    hasPathSum(root.left, sum - root.val) ||
    hasPathSum(root.right, sum - root.val)
  )
}
@sl1673495 sl1673495 added DFS 深度优先遍历 二叉树 待复习 看题解或者做出来很艰难的,需要回顾。 例题详解 每个分类下会挑出几道题目进行精讲,其他的同类题目会默认拥有这些前置知识而简略讲解。 labels Jun 6, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
DFS 深度优先遍历 二叉树 例题详解 每个分类下会挑出几道题目进行精讲,其他的同类题目会默认拥有这些前置知识而简略讲解。 待复习 看题解或者做出来很艰难的,需要回顾。
Projects
None yet
Development

No branches or pull requests

1 participant