给定一个二叉树，找出所有路径中各节点相加总和等于给定 目标值 的路径。 一个有效的路径，指的是从根节点到叶节点的路径。

image.png

唯一的解法就是，遍历所有结果。
优化点就是，一旦出现 到某个节点，点数超过所要找的值，就放弃该节点，和所有它的子节点。

狗屁。

class Solution:
    """
    @param: root: the root of binary tree
    @param: target: An integer
    @return: all valid paths
    """
    a = []
    temp = []
    def binaryTreePathSum(self, root, target):
        # write your code here
        self.left(root,target,0)
        return self.a
    def left(self,root,target,total):
        if root == None:
            if total == target:
                self.a.append(copy(self.temp))
            return
        self.temp.append(root.val)
        self.left(root.left,target,total+root.val)
        if len(self.temp) != 0:   ####这里有错
                self.temp.pop()
        self.right(root.right,target,total+root.val)
    def right(self,root,target,total):
        if root == None:
            return
        self.temp.append(root.val)
        self.left(root.left,target,total+root.val)
        self.right(root.right,target,total+root.val)

写了一天。2017.11.15。错误在不熟递归。关键在从大体出发。

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
def copy(tlist):
    a = []
    for i in tlist:
        a.append(i)
    return a

class Solution:
    """
    @param: root: the root of binary tree
    @param: target: An integer
    @return: all valid paths
    """
    a = []
    temp = []
    def binaryTreePathSum(self, root, target):
        # write your code here
        self.left(root,target,0)
        return self.a
    def left(self,root,target,total):
        if root == None:
            print(total,self.temp)
            if total == target:
                self.a.append(copy(self.temp))
            return
        self.temp.append(root.val)
        self.left(root.left,target,total+root.val)
        self.right(root.right,target,total+root.val)
        if len(self.temp) != 0:
                self.temp.pop()
    def right(self,root,target,total):
        if root == None:
            return
        self.temp.append(root.val)
        self.left(root.left,target,total+root.val)
        self.right(root.right,target,total+root.val)
        if len(self.temp) != 0:
                self.temp.pop()