image.png

唯一的解法就是庸疾，遍歷所有結(jié)果乍楚。
優(yōu)化點就是，一旦出現(xiàn) 到某個節(jié)點届慈，點數(shù)超過所要找的值徒溪，就放棄該節(jié)點凌箕，和所有它的子節(jié)點。

狗屁词渤。

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。錯誤在不熟遞歸缺虐。關(guān)鍵在從大體出發(fā)芜壁。

"""
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()