Leetcode # 894. All Possible Full Binary Trees

https://leetcode.com/problems/all-possible-full-binary-trees

Solution

n 個節點的 Full Binary Tree 種類數是 C_{(n – 1) / 2}
C_{(n – 1) / 2} 亦是 time complexity
而每一種 Full Binary Tree 都會花費 n 的空間建立
所以 space complexity 為 nC_{(n – 1) / 2}
考慮 output 所需空間不計入的情況下則為O(1)

Time Complexity: O(C_{(n – 1) / 2})
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
    def all_possible_fbt(n):
      roots = []
      if n % 2 != 1:
        return []
      if n == 1:
        return [TreeNode(0)]
      rest = n - 1
      for left in range(1, rest, 2):
        right = rest - left
        for l_root in all_possible_fbt(left):
          for r_root in all_possible_fbt(right):
            roots.append(TreeNode(0, l_root, r_root))
      return roots
    return all_possible_fbt(n)

Last Updated on 2023/08/16 by A1go