Question

894. All Possible Full Binary Trees

中文文档

Description

Given an integer n, return _a list of all possible full binary trees with_ n _nodes_. Each node of each tree in the answer must have Node.val == 0.

Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order.

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

 

Example 1:

Input: n = 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

Example 2:

Input: n = 3
Output: [[0,0,0]]

 

Constraints:

• 1 <= n <= 20

Solutions

Solution 1

# Definition for a binary tree node.
# class TreeNode:
#   def __init__(self, val=0, left=None, right=None):
#     self.val = val
#     self.left = left
#     self.right = right
class Solution:
  def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
    @cache
    def dfs(n: int) -> List[Optional[TreeNode]]:
      if n == 1:
        return [TreeNode()]
      ans = []
      for i in range(n - 1):
        j = n - 1 - i
        for left in dfs(i):
          for right in dfs(j):
            ans.append(TreeNode(0, left, right))
      return ans

    return dfs(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val;
 *     this.left = left;
 *     this.right = right;
 *   }
 * }
 */
class Solution {
  private List<TreeNode>[] f;

  public List<TreeNode> allPossibleFBT(int n) {
    f = new List[n + 1];
    return dfs(n);
  }

  private List<TreeNode> dfs(int n) {
    if (f[n] != null) {
      return f[n];
    }
    if (n == 1) {
      return List.of(new TreeNode());
    }
    List<TreeNode> ans = new ArrayList<>();
    for (int i = 0; i < n - 1; ++i) {
      int j = n - 1 - i;
      for (var left : dfs(i)) {
        for (var right : dfs(j)) {
          ans.add(new TreeNode(0, left, right));
        }
      }
    }
    return f[n] = ans;
  }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  vector<TreeNode*> allPossibleFBT(int n) {
    vector<vector<TreeNode*>> f(n + 1);
    function<vector<TreeNode*>(int)> dfs = [&](int n) -> vector<TreeNode*> {
      if (f[n].size()) {
        return f[n];
      }
      if (n == 1) {
        return vector<TreeNode*>{new TreeNode()};
      }
      vector<TreeNode*> ans;
      for (int i = 0; i < n - 1; ++i) {
        int j = n - 1 - i;
        for (auto left : dfs(i)) {
          for (auto right : dfs(j)) {
            ans.push_back(new TreeNode(0, left, right));
          }
        }
      }
      return f[n] = ans;
    };
    return dfs(n);
  }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */
func allPossibleFBT(n int) []*TreeNode {
  f := make([][]*TreeNode, n+1)
  var dfs func(int) []*TreeNode
  dfs = func(n int) []*TreeNode {
    if len(f[n]) > 0 {
      return f[n]
    }
    if n == 1 {
      return []*TreeNode{&TreeNode{Val: 0}}
    }
    ans := []*TreeNode{}
    for i := 0; i < n-1; i++ {
      j := n - 1 - i
      for _, left := range dfs(i) {
        for _, right := range dfs(j) {
          ans = append(ans, &TreeNode{0, left, right})
        }
      }
    }
    f[n] = ans
    return ans
  }
  return dfs(n)
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   val: number
 *   left: TreeNode | null
 *   right: TreeNode | null
 *   constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 *   }
 * }
 */

function allPossibleFBT(n: number): Array<TreeNode | null> {
  const f: Array<Array<TreeNode | null>> = new Array(n + 1).fill(0).map(() => []);
  const dfs = (n: number): Array<TreeNode | null> => {
    if (f[n].length) {
      return f[n];
    }
    if (n === 1) {
      f[n].push(new TreeNode(0));
      return f[n];
    }
    const ans: Array<TreeNode | null> = [];
    for (let i = 0; i < n - 1; ++i) {
      const j = n - 1 - i;
      for (const left of dfs(i)) {
        for (const right of dfs(j)) {
          ans.push(new TreeNode(0, left, right));
        }
      }
    }
    return (f[n] = ans);
  };
  return dfs(n);
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//   TreeNode {
//     val,
//     left: None,
//     right: None
//   }
//   }
// }

impl TreeNode {
  pub fn new_with_node(
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>
  ) -> Self {
    Self {
      val: 0,
      left,
      right,
    }
  }
}

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  #[allow(dead_code)]
  pub fn all_possible_fbt(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
    let mut record_vec = vec![vec![]; n as usize + 1];
    Self::dfs(n, &mut record_vec)
  }

  #[allow(dead_code)]
  fn dfs(
    n: i32,
    record_vec: &mut Vec<Vec<Option<Rc<RefCell<TreeNode>>>>>
  ) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
    if record_vec[n as usize].len() != 0 {
      return record_vec[n as usize].clone();
    }
    if n == 1 {
      // Just directly return a single node
      return vec![Some(Rc::new(RefCell::new(TreeNode::new(0))))];
    }
    // Otherwise, need to construct return vector
    let mut ret_vec = Vec::new();

    // Enumerate the node number for left subtree from 0 -> n - 1
    for i in 0..n - 1 {
      // The number of right subtree node
      let j = n - i - 1;
      for left in Self::dfs(i, record_vec) {
        for right in Self::dfs(j, record_vec) {
          // Construct the ret vector
          ret_vec.push(
            Some(
              Rc::new(
                RefCell::new(TreeNode::new_with_node(left.clone(), right.clone()))
              )
            )
          );
        }
      }
    }

    record_vec[n as usize] = ret_vec;

    record_vec[n as usize].clone()
  }
}