分治&dp，LeetCode 894. 所有可能的真二叉树

给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。

答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。

真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。

2、接口描述

cpp

/**
 * 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) {

    }
};

python3

# 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]]:

3、原题链接

894. 所有可能的真二叉树

二、解题报告

1、思路分析

F1 回溯

首先对于偶数个节点的情况直接返回空即可

然后分析，对于n（n为奇数）个节点的二叉树，根节点占一个节点，那么其左右节点的情况为

<1, n - 2>, <3, n - 4>……

所以我们发现构造n个节点的真二叉树可以分治为构造两个子真二叉树的问题

所以我们枚举左右儿子的节点数目进行分治构造即可

F2 动态规划

我们可以换种思路，自底向上分析

对于n个节点的真二叉树可以分为根节点加上两个子真二叉树

同样的，我们也可以由两个子真二叉树构造出一棵真二叉树

我们设f[k]（k >= 1）为n = 2 * k - 1个节点的真二叉树的所有可能序列

那么f[i] = node(f[k], f[i - k])，这个递推还是比较简单的

相较于分治的做法，时间复杂度并未降低，但是省去了递归开销

由于数据量只到20，因此我们可以预处理出f[1]~f[10]

2、复杂度

分治：时间复杂度： $O(\frac{4_{}^{n}}{n_{}^{3/2}})$ 空间复杂度： $O(\frac{4_{}^{n}}{n_{}^{3/2}})$

dp：预处理时间复杂度 $O(\frac{4_{}^{N}}{N_{}^{3/2}})$ 预处理空间复杂度： $O(\frac{4_{}^{N}}{N_{}^{3/2}})$ ，N = 11

查询的时间复杂度和空间复杂度都是O(1)

3、代码详解

分治

cpp

/**
 * 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<TreeNode*> ret;
        if(n % 2 == 0) return ret;
        if(n == 1) return {new TreeNode(0)};
        for(int i = 1; i < n; i += 2){
            vector<TreeNode*> leftnodes(allPossibleFBT(i)), rightnodes(allPossibleFBT(n - i - 1));
            for(TreeNode* x : leftnodes)
                for(TreeNode* y : rightnodes)
                    ret.emplace_back(new TreeNode(0, x, y));
        }
        return ret;
    }
};

python3

# 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]]:
        if n % 2 == 0:
            return []
        if n == 1:
            return [TreeNode()]
        ret = []
        for i in range(1, n, 2):
            leftnodes, rightnodes = self.allPossibleFBT(i), self.allPossibleFBT(n - i - 1)
            ret.extend([TreeNode(0, x, y) for x in leftnodes for y in rightnodes])
        return ret

python也可以记忆化搜索，得到和dp相媲美的效率

# 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:
    @cache
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        if n % 2 == 0:
            return []
        if n == 1:
            return [TreeNode()]
        ret = []
        for i in range(1, n, 2):
            leftnodes, rightnodes = self.allPossibleFBT(i), self.allPossibleFBT(n - i - 1)
            ret.extend([TreeNode(0, x, y) for x in leftnodes for y in rightnodes])
        return ret

dp

cpp

/**
 * 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];
bool init = []{
    f[1] = { new TreeNode() };
    for(int i = 2; i < 11; i++)
        for(int j = 1; j < i; j++)
            for(TreeNode* x : f[j])
                for(TreeNode* y : f[i - j])
                    f[i].emplace_back(new TreeNode(0, x, y));
    return false;
}();
class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int n) {
        return f[n & 1 ? (n + 1) / 2 : 0];
    }
};

python3

# 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
f = [[] for _ in range(11)]
f[1] = [TreeNode()]
for i in range(2, 11):
    f[i] = [TreeNode(0, x, y) 
            for j in range(1, i)
                for x in f[j]
                    for y in f[i - j]]
class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        return f[(n + 1) // 2] if n & 1 else []

原文地址:https://blog.csdn.net/EQUINOX1/article/details/137261507 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1775540774398726144.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部