给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明:叶子节点是指没有子节点的节点。
示例：
给定如下二叉树，以及目标和sum=22.
二叉树图1
返回true，因为存在目标和为22的根节点到叶子节点的路径5->4->11>2.
经过这几天树结构的题讲解，是不是现在看到树就直接用递归了。没错下面介绍第一种算法就是使用递归来实现。
方法1：递归
最直接的方法就是递归，遍历整棵树：如果当前节点不是叶子，对它的所有孩子节点，递归调用hasPathSum 函数，其中sum值减去当前节点的值；如果当前节点是叶子，检查sum值是否为0，也就是是否找到了给定的目标和。
递归实现图2
方式2：递归2
方式1使用的减法，咱们也可以使用加法来做，同样也是递归调用，判断当前是否是叶子节点，如果是叶子节点，就直接判断当前值加上父节点以前的总和是不是等于目标和；反之就递归求取左子节点和右子节点是否满足，来判断结果值是否成立。
递归实现图3
方式3：迭代
我们可以用栈将递归转成迭代的形式。深度优先搜索在除了最坏情况下都比广度优先搜索更快。最坏情况是指满足目标和的路径最后考虑，这种情况下深度优先和广度优先代价是相通的。
利用深度优先策略访问每个节点，同时更新剩余的目标和。
所以我们从根节点的栈开始模拟，剩余目标和为sum-root.val。
然后开始迭代：弹出当前元素，如果当前剩余目标和为 0 并且在叶子节点上返回 True；如果剩余和不为零并且还处在非叶子节点上，将当前节点的所有孩子以及对应的剩余和压入栈中。
迭代实现图4
今天又是收获满满的一天，对于树的理解更加深入，以后独自面对树结构类型的题都能游刃有余的解决掉。
恩哈，又到了最后一段，相信大家每次看到这句话的时候，反手就是一个删除。。。当然了，我还是要秉着一贯不要face的恳请大家关注下公众号了，当然微信私信也是可以的。
网友评论