rust 解法, 执行用时: 10 ms, 内存消耗: 3.2 MB, 提交时间: 2024-04-02 09:34:17

// 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
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn all_possible_fbt(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        if n % 2 == 0 {
            return vec![];
        }
        let n = (n as usize + 1) / 2;
        let mut f = vec![vec![]; n + 1];
        f[1].push(Some(Rc::new(RefCell::new(TreeNode::new(0)))));
        for i in 2..f.len() { // 计算 f[i]
            let mut fi = vec![];
            for j in 1..i { // 枚举左子树叶子数
                for left in &f[j] { // 枚举左子树
                    for right in &f[i - j] { // 枚举右子树
                        fi.push(Some(Rc::new(RefCell::new(TreeNode { val: 0, left: left.clone(), right: right.clone() }))));
                    }
                }
            }
            f[i] = fi;
        }
        f[n].clone()
    }
}

javascript 解法, 执行用时: 123 ms, 内存消耗: 60.3 MB, 提交时间: 2024-04-02 09:34:01

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
const f = Array.from({length: 11}, () => []);
f[1].push(new TreeNode());
for (let i = 2; i < f.length; i++) { // 计算 f[i]
    for (let j = 1; j < i; j++) { // 枚举左子树叶子数
        for (const left of f[j]) { // 枚举左子树
            for (const right of f[i - j]) { // 枚举右子树
                f[i].push(new TreeNode(0, left, right));
            }
        }
    }
}

var allPossibleFBT = function(n) {
    return f[n % 2 ? (n + 1) / 2 : 0];
};

golang 解法, 执行用时: 12 ms, 内存消耗: 8 MB, 提交时间: 2024-04-02 09:33:44

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var f = [11][]*TreeNode{1: {{}}}

func init() {
    for i := 2; i < len(f); i++ { // 计算 f[i]
        for j := 1; j < i; j++ {  // 枚举左子树叶子数
            for _, left := range f[j] { // 枚举左子树
                for _, right := range f[i-j] { // 枚举右子树
                    f[i] = append(f[i], &TreeNode{0, left, right})
                }
            }
        }
    }
}

func allPossibleFBT(n int) []*TreeNode {
    if n%2 > 0 {
        return f[(n+1)/2]
    }
    return nil
}

cpp 解法, 执行用时: 58 ms, 内存消耗: 29.8 MB, 提交时间: 2024-04-02 09:33:20

/**
 * 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) {}
 * };
 */
vector<TreeNode*> f[11];

auto init = [] {
    f[1] = {new TreeNode()};
    for (int i = 2; i < 11; i++) { // 计算 f[i]
        for (int j = 1; j < i; j++) { // 枚举左子树叶子数
            for (auto left : f[j]) { // 枚举左子树
                for (auto right : f[i - j]) { // 枚举右子树
                    f[i].push_back(new TreeNode(0, left, right));
                }
            }
        }
    }
    return 0;
}();

class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int n) {
        return f[n % 2 ? (n + 1) / 2 : 0];
    }
};

java 解法, 执行用时: 4 ms, 内存消耗: 44.7 MB, 提交时间: 2024-04-02 09:32:59

/**
 * 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 static final List<TreeNode>[] f = new ArrayList[11];

    static {
        Arrays.setAll(f, i -> new ArrayList<>());
        f[1].add(new TreeNode());
        for (int i = 2; i < f.length; i++) { // 计算 f[i]
            for (int j = 1; j < i; j++) { // 枚举左子树叶子数
                for (TreeNode left : f[j]) { // 枚举左子树
                    for (TreeNode right : f[i - j]) { // 枚举右子树
                        f[i].add(new TreeNode(0, left, right));
                    }
                }
            }
        }
    }

    public List<TreeNode> allPossibleFBT(int n) {
        return f[n % 2 > 0 ? (n + 1) / 2 : 0];
    }
}

python3 解法, 执行用时: 66 ms, 内存消耗: 20.1 MB, 提交时间: 2024-04-02 09:32:36

# 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

MX = 11
f = [[] for _ in range(MX)]
f[1] = [TreeNode()]
for i in range(2, MX):  # 计算 f[i]
    f[i] = [TreeNode(0, left, right)
            for j in range(1, i)  # 枚举左子树叶子数
            for left in f[j]  #  枚举左子树
            for right in f[i - j]]  # 枚举右子树

class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        return f[(n + 1) // 2] if n % 2 else []

python3 解法, 执行用时: 96 ms, 内存消耗: 19.1 MB, 提交时间: 2022-11-15 10:54:14

# 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(object):
    memo = {0: [], 1: [TreeNode(0)]}

    def allPossibleFBT(self, n: int):
        if n not in Solution.memo:
            ans = []
            for x in range(n):
                y = n - 1 - x
                for left in self.allPossibleFBT(x):
                    for right in self.allPossibleFBT(y):
                        bns = TreeNode(0)
                        bns.left = left
                        bns.right = right
                        ans.append(bns)
            Solution.memo[n] = ans

        return Solution.memo[n]