437. 路径总和 III

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        dp = {}
        
        def search(root: TreeNode): 
            if root:
                search(root.left)
                search(root.right)
                a = b = []
                if root.left:
                    a = dp[root.left]
                if root.right:
                    b = dp[root.right]
                temp = [root.val]
                for t in a:
                    temp.append(root.val + t)
                for t in b:
                    temp.append(root.val + t)
                dp[root] = temp
        search(root)
        k = 0 # 统计目标值
        for r, val in dp.items():
            for t in val:
                if t == sum:
                    k += 1
        return k

889. 根据前序和后序遍历构造二叉树

class Solution:
    def constructFromPrePost(self, pre: List[int], post: List[int]) -> TreeNode:
        if not pre:
            return None
        node = TreeNode(pre[0])
        if len(pre) == 1:
            return node
        idx = post.index(pre[1])
        node.left = self.constructFromPrePost(pre[1:idx+2], post[:idx+1])
        node.right = self.constructFromPrePost(pre[idx+2:], post[idx+1:-1])
        return node