递归

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        result = []
        path = []
        self.path_method(root, result, path, expectNumber)
        return result

    def path_method(self, root, result, path, expectNumber):
        if root:
            path.append(root.val)
            if not root.left and not root.right and sum(path) == expectNumber:
                result.append([i for i in path])
            self.path_method(root.left, result, path, expectNumber)
            self.path_method(root.right, result, path, expectNumber)
            path.pop()


root = TreeNode(10)
mid = TreeNode(5)
root.left = mid
root.right = TreeNode(12)
mid.left = TreeNode(4)
mid.right = TreeNode(7)
s = Solution()
print(s.FindPath(root, 22))

非递归

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        result = []
        stack = []
        pre = None
        while stack or root:
            if root:
                stack.append(root)
                temp = [i.val for i in stack]
                if not root.left and not root.right and sum(temp) == expectNumber:
                    result.append(temp)
                root = root.left
            else:
                temp_node = stack[-1]
                if temp_node.right and temp_node.right != pre:
                    root = temp_node.right
                else:
                    pre = stack.pop()
        return result