Python每日一练(20230421) 组合总和II、加一、中后序遍历构造二叉树

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        dp = [[] for _ in range(target + 1)]
        dp[0].append([])
        for i in range(1, target + 1):
            for j in range(len(candidates)):
                if candidates[j] > i:
                    break
                for k in range(len(dp[i - candidates[j]])):
                    temp = dp[i - candidates[j]][k][:]
                    if len(temp) > 0 and temp[-1] >= j:
                        continue
                    temp.append(j)
                    dp[i].append(temp)
        res = []
        check = {}
        for temp in dp[target]:
            value = [candidates[t] for t in temp]
            try:
                check[str(value)] += 1
            except KeyError:
                check[str(value)] = 1
                res.append(value)
        return res
# %%
s = Solution()
print(s.combinationSum2(candidates = [10,1,2,7,6,1,5], target = 8))
print(s.combinationSum2(candidates = [2,5,2,1,2], target = 5))

class Solution(object):
    def plusOne(self, digits):
        ls = len(digits)
        for index in reversed(range(ls)):
            if digits[index] < 9:
                digits[index] += 1
                return digits
            else:
                digits[index] = 0
        digits.insert(0, 1)
        return digits
# %%
s = Solution()
print(s.plusOne(digits = [1,2,3]))
print(s.plusOne(digits = [4,3,2,1]))
print(s.plusOne(digits = [0]))
print(s.plusOne(digits = [9,9,9]))

from typing import List
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
    def levelOrder(self):
        if not self: return []
        res, que = [], [self]
        while que:
            cur = que.pop(0)
            if cur:
                res.append(cur.val) 
                que.append(cur.left)
                que.append(cur.right)
            else:
                res.append(None)
        while res[-1] is None:
            res.pop()
        return res
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        def build_tree(in_left, in_right, post_left, post_right):
            if in_left > in_right:
                return
            post_root = post_right
            root = TreeNode(postorder[post_root])
            in_root = inorder_map[root.val]
            size_of_left = in_root - in_left
            root.left = build_tree(
                in_left, in_root - 1, post_left, post_left + size_of_left - 1
            )
            root.right = build_tree(
                in_root + 1, in_right, post_left + size_of_left, post_root - 1
            )
            return root
        size = len(inorder)
        inorder_map = {}
        for i in range(size):
            inorder_map[inorder[i]] = i
        return build_tree(0, size - 1, 0, size - 1)
#%%
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
s = Solution()
print(s.buildTree(inorder, postorder).levelOrder())