给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
给定如下二叉树,以及目标和sum = 22
,返回true
,因为存在目标和为22
的根节点到叶子节点的路径5->4->11->2
。
深度优先遍历即可,首先处理边界条件,如果节点为null
则直接返回false
,之后将tmp
值与节点值相加,如果此节点为根节点,那么就返回tmp
是否与sum
相等的判断,最后进行深度递归遍历,利用短路运算效应,在左子树为true
的情况下不会再进行右子树的递归运算,在右子树为true
的情况下会直接返回上层递归运算,这样即可实现路径总和的计算。