我好像洞察到二叉树路径和的秘密

在力扣上面，二叉树路径和一直是一块很大的问题，通过各种方法遍历二叉树，寻找到想要的路径，这种方法就叫路径和，那么，通过什么样的解法去思考呢。

1，递归

递归主要就是递归公式和结束条件的选择。这里有如下两条方法。

class solution:
    def func(root,target):
        if not root:
            return target
\
 
 
class solution:
    def func(root,target):
        if not root.left and not root.right:
            return target

在不去看其他条件的情况下，这两个结束条件有什么区别第一个是当遍历完所有的root，也即当前所在的节点为TreeNode(None)的时候进行输出，另外一个是在叶子节点的时候进行输出。

第一个的好处当然是可以覆盖掉root为空的情况，当你给进去的一个值是空的，这一下子就输出，但是坏处呢，就是无法向上递归，遍历是遍历了，可是寻找上一节点还有些问题。虽然二叉树没有这方面问题。

那么下面的判断条件其实也要进行调换。尤其是前面一个的话，只能等到递归为空的时候才进行判断，缺少很多灵活性，而当递归到叶子节点在进行判断的话，选择性多很多。

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def recur(root,target):
            if not root and target == 0:
                return True
            if not root:return False
 
            target-= root.val
            return recur(root.left, target) or recur(root.right, target)
        if not root:return False
        return recur(root,targetSum)

class soluttion:
    def func(root,target):
        if not root:return False
        if not root.left and not root.right:
            return target == root.val
 
        return func(root.left,target - root.val) or func(root.right, target - root.val)

以上两个就是用于两个不同判断条件写出来的代码，第一个不能完全覆盖力扣的测试用例，不知道是啥情况。

可以用队列去做的话，思路差不多，在队列中加入一个root.val项目。

class solution:
    def queue(root,target):
        if not root:return False
        que = [(root, root.val)]
        while que:
            root, path = que.pop(0)
            if not root.left and not root.right:
                return path == target
 
            if root.left:
                que += [(root.left, root.left.val + path)]
            if root.right:
                que += [(root.right, root.right + path)]

这里有几个坑，首先，做这种路径判断建议是用叶子节点去判断。千万别去判断为空的情况。

所以结束条件是：

if not root.left and not root.right and path == targetSum:
    return True

并且在末尾加上return False

栈跟队列差不对的解法。

本法参考力扣负雪明烛的解法。