题目#112.路径总和

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

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

示例:
给定如下二叉树，以及目标和 sum = 22，

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

题目分析

题目指出从根节点到叶子节点，也就相当于限制了起始条件以及递归函数的退出条件，我们可以使用回溯的思想，来完成题目，具体代码如下。

代码

fun hasPathSum(root: TreeNode?, sum: Int): Boolean {
    if (root == null) return false
    if (root.left == null && root.right == null) return root.`val` == sum
    return hasPathSum(root.right, sum - root.`val`) || hasPathSum(root.left, sum - root.`val`)
}

代码分析

类似这种二叉树问题，基本上需要用到递归，而我们只需要找到递归结束条件，以及递归结构体即可。

寻找递归结束条件

在题目中有明显的提示:

叶子节点是指没有子节点的节点

• 得到递归结束条件1：左右子树均为空if (root.left == null && root.right == null)
  同样，如果没有节点，哪里来的左右自己子节点呢？
• 得到递归结束条件2：输入节点是否为空if (root == null)
  同样根据题目描述:

判断该树中是否存在根节点到叶子节点的路径

存在这两个字翻译成程序语言不就是或吗。

• 得到递归结束条件3：或表达式

填充递归结构体

递归结构体分别对应循环结束条件

• 对于条件1，如果根节点值为目标值，那就返回存在：return root.`val` == sum
• 对于条件2，如果根节点不存在，那必然不存在：return false
• 对于条件3，只要存在其中一个子节点满足，那必然存在：return hasPathSum(root.right, sum - root.`val`) || hasPathSum(root.left, sum - root.`val`)
  这里需要将sum移除根节点的值，因为题中明确表示值要从根节点开始，如果我们从子节点开始寻找，就需要移除对应的根节点值。