利用后序遍历求解

为了求解路径，我们可以将目标数减去每一个路过的节点的值（剩余值），到达一个叶节点时，若剩余值减至为0，则包含该叶节点的路径为一个解。

树的后序遍历的顺序是左子树、右子树和根节点。利用后序遍历，我们可以无需在入栈每个节点时将到达该节点的路径一同入栈，降低了空间复杂度。相反，对每一个节点，在入栈时，我们只需要记录该节点和其对应的剩余值即可。
当出现满足条件的路径时，我们只需将栈中从栈底到栈顶的元素依次输出，加上叶节点的值，存入最终结果即可。

注意：此法无法用前序和中序来求解，因为根节点的剩余值对左右子树的遍历是必要的，所以根节点要最后访问。

# -*- coding:utf-8 -*-
# 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
        if not root:    return []
        cur = root
        paths = []
        v = []
        cnt = expectNumber
        pre = None
        while cur:
            cnt -= cur.val
            v.append([cur, cnt])
            cur = cur.left
        while v:
            cur, cnt = v.pop()
            if not cur.right or cur.right == pre:
                pre = cur
                if not cur.left and not cur.right and cnt == 0:
                    paths.append([])
                    for node in v:
                        paths[-1].append(node[0].val)
                    paths[-1].append(cur.val)
            else:
                v.append([cur, cnt])
                cur = cur.right
                while cur:
                    cnt -= cur.val
                    v.append([cur, cnt])
                    cur = cur.left
        return paths