894. All Possible Full Binary Trees

今天第一次正式参加 leetcode 每周的 contest，好激动。

# 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)]
        if N == 2: return []

        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:
                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 *= 2
        return cur_res

主要错误

1. 在左右为空的时候，没有更新 i

            if not left or not right:
                continue

1. 对构成 full binary tree 的条件表达错误

我最初的理解是 $2^m - 1$ 的数才能构成 full binary tree。 但是，其实是 $2 * m - 1$