894. All Possible Full Binary Trees

今天参加了一个 leetcode 每周的 contest，哈哈小激动。

这个题用了 hash table 保存中间结果，反到变慢了。。。

Use hash table to reduce repeat N nodes.

Runtime: 396 ms

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def allPossibleFBT(self, N):
        """
        :type N: int
        :rtype: List[TreeNode]
        """
        table = {
            0: [],
            1: [TreeNode(0)]
        }
        def helper(N):
            if N in table: return table[N]

            cur_res = []
            i = 1
            while (i * 2 - 1) < N:
                left = self.allPossibleFBT(i * 2 - 1)
                right = self.allPossibleFBT(N - 1 - i * 2 + 1)
                if not left or not right:
                    i += 1
                    continue
                for l in left:
                    for r in right:
                        cur_root = TreeNode(0)
                        cur_root.left = l
                        cur_root.right = r
                        cur_res.append(cur_root)
                i += 1
            table[N] = cur_res
            return cur_res
        return helper(N)

Without hash table

Runtime: 352 ms

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def allPossibleFBT(self, N):
        """
        :type N: int
        :rtype: List[TreeNode]
        """
        if N == 0: return []
        if N == 1: return [TreeNode(0)]

        cur_res = []
        i = 1
        while (i * 2 - 1) < N:
            left = self.allPossibleFBT(i * 2 - 1)
            right = self.allPossibleFBT(N - 1 - i * 2 + 1)
            if not left or not right:
                i += 1
                continue
            for l in left:
                for r in right:
                    cur_root = TreeNode(0)
                    cur_root.left = l
                    cur_root.right = r
                    cur_res.append(cur_root)
            i += 1

        return cur_res