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:
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| # 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| /**
* 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| /**
* 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);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| /**
* 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)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| /**
* 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);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| // 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()
}
}
|
