leetcode 【路径之和112 113 所有路径257】Python

**leetcode 112**是给定特定int类型targetSum，返回是否存在一条路径使得路径上所有节点的和等于targetSum。
**leetcode 113**也是给定特定int类型targetSum，返回所有和等于targetSum的路径。
**leetcode 257**是返回二叉树的所有路径，路径表达形式是字符串’1->2->3’这样

第一句
que=deque([ (root , xxx yyy) ])
这是一个双端队列，所有初始化的时候是一个[]，然后第一个元素一般不止一个root，通常还有一些其他的变量，所以是一个元组。后面在循环的时候，每次也是append一个元组。
或者que=collectios.deque()
然后是
while que:
	node, x, y = que.popleft()
	。。。
	if not node.left and not node.right:
	叶子节点
	if node.left:
		que.append((node.left, aaa, bbb))
	if node.right:
		que.append((node.right, ccc, ddd))
至于while循环中的return和while循环之外的return，视情况定

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root is None:
            return False
        que=deque([ root, root.val])
        while que:
        	node, current_sum=que.popleft()
        	#if not node.left and not node.right:
        	#	return current_sum==targetSum
            上面两句不能这么写，如果第一个碰到False就直接return了
            那么后面还有True的路径怎么办？
            所以需要下面这样写
            if not node.left and not node.right and current_sum==targetSum:
        		return True
        	像上面这样写，然后最后while循环结束的时候加一个return False
        	保证如果所有路径都没True，那就说明所有路径都是False
        	if node.left:
        		que.append((node.left, current_sum+node.left.val))
        	if node.right:
        		que.append((node.right, current_sum+node.right.val))
        return False
        	

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        if not root:
            return []
        res = []
        que=deque([(root, [root.val], root.val)]) # 初始化当前节点 当前路径 当前路径和
        while que:
            node,path,curr_sum=que.popleft() # bfs的经典套路模板
            if not node.left and not node.right and curr_sum==sum:
                res.append(path)
            if node.left:
                que.append((node.left,path+[node.left.val],curr_sum+node.left.val))
            if node.right:
                que.append((node.right,path+[node.right.val],curr_sum+node.right.val))
        return res 

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
		if not root:
        	return []
        res=[]
        que=deque([(root, [str(root.val)])]) #初始化节点 字符串
        while que:
        	node, path= que.popleft()
        if not node.left and not node.right:
        	res.append(path)
        if node.left:
        	que.append(node.left, path+'->'+str(node.left.val))
        if node.right:
        	que.append(node.right, path+'->'+str(node.right.val))
       	return res