Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/894.html
894. All Possible Full Binary Trees (Medium)
A full binary tree is a binary tree where each node has exactly 0 or 2 children.
Return a list of all possible full binary trees with N
nodes. Each element of the answer is the root node of one possible tree.
Each node
of each tree in the answer must have node.val = 0
.
You may return the final list of trees in any order.
Example 1:
Input: 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]] Explanation:![]()
Note:
1 <= N <= 20
Companies:
Google
Related Topics:
Tree, Recursion
Solution 1.
-
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<TreeNode> allPossibleFBT(int N) { if (N % 2 == 0) return new ArrayList<TreeNode>(); Map<Integer, List<TreeNode>> map = new HashMap<Integer, List<TreeNode>>(); List<TreeNode> oneList = new ArrayList<TreeNode>(); oneList.add(new TreeNode(0)); map.put(1, oneList); for (int i = 3; i <= N; i += 2) { List<TreeNode> curList = map.getOrDefault(i, new ArrayList<TreeNode>()); int sum = i - 1; for (int left = 1; left < sum; left++) { int right = sum - left; List<TreeNode> leftList = map.getOrDefault(left, new ArrayList<TreeNode>()); List<TreeNode> rightList = map.getOrDefault(right, new ArrayList<TreeNode>()); for (TreeNode leftNode : leftList) { for (TreeNode rightNode : rightList) { TreeNode root = new TreeNode(0); root.left = leftNode; root.right = rightNode; curList.add(root); } } } map.put(i, curList); } return map.get(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 = new List[21]; public List<TreeNode> allPossibleFBT(int n) { return dfs(n); } private List<TreeNode> dfs(int n) { if (f[n] != null) { return f[n]; } if (n == 1) { return Collections.singletonList(new TreeNode()); } List<TreeNode> res = new ArrayList<>(); for (int i = 0; i < n - 1; ++i) { int j = n - i - 1; for (TreeNode left : dfs(i)) { for (TreeNode right : dfs(j)) { res.add(new TreeNode(0, left, right)); } } } f[n] = res; return res; } }
-
// OJ: https://leetcode.com/problems/all-possible-full-binary-trees/ // Time: O(2^N) // Space: O(2^N) class Solution { public: vector<TreeNode*> allPossibleFBT(int N) { if (N % 2 == 0) return {}; if (N == 1) return { new TreeNode(0) }; vector<TreeNode*> ans; for (int i = 1; i <= N - 2; i += 2) { auto lefts = allPossibleFBT(i); auto rights = allPossibleFBT(N - i - 1); for (auto left : lefts) { for (auto right : rights) { auto root = new TreeNode(0); root->left = left; root->right = right; ans.push_back(root); } } } return ans; } };
-
# 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): if n == 1: return [TreeNode()] res = [] if n % 2: for i in range(n - 1): j = n - i - 1 for left in dfs(i): for right in dfs(j): res.append(TreeNode(0, left, right)) return res return dfs(n) ############ # 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] """ N -= 1 if N == 0: return [TreeNode(0)] res = [] for l in range(1, N, 2): for left in self.allPossibleFBT(l): for right in self.allPossibleFBT(N - l): node = TreeNode(0) node.left = left node.right = right res.append(node) return res
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func allPossibleFBT(n int) []*TreeNode { f := map[int][]*TreeNode{} var dfs func(n int) []*TreeNode dfs = func(n int) []*TreeNode { if v, ok := f[n]; ok { return v } if n == 1 { return []*TreeNode{&TreeNode{Val: 0} } } res := []*TreeNode{} for i := 0; i < n-1; i++ { j := n - i - 1 for _, left := range dfs(i) { for _, right := range dfs(j) { res = append(res, &TreeNode{0, left, right}) } } } f[n] = res return res } 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() } }