动态规划 | 分治法 -- 所有可能的真二叉树-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划 | 分治法 -- 所有可能的真二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

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

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

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

示例 1：

动态规划 | 分治法 -- 所有可能的真二叉树,算法题,动态规划,算法,leetcode,java

输入：n = 7
输出：[[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]]

示例 2：

输入：n = 3
输出：[[0,0,0]]

提示：

1 <= n <= 20

1. 分治

1.1 算法与思路

根据题意可知，真二叉树中的每个结点的子结点数是 0 或 2，此时可以推出真二叉树中的结点数 n 为奇数，可以使用数学归纳法证明：

当真二叉树中只有 1 个结点时，此时 1 为奇数，树中唯一的结点是根结点，。

当真二叉树中有 n 个结点时，根据真二叉树的定义，此时可将其中一个叶结点增加两个子结点之后仍为真二叉树，新的真二叉树中有 n+2 个结点，由于 n 是奇数，此时 n+2 也是奇数。

由于真二叉树中的结点数一定是奇数，因此当给定的节点数 n 是偶数时，此时无法构成真二叉树，返回空值即可。当真二叉树节点数目 n 大于 1 时，此时真二叉树的左子树与右子树也一定为真二叉树，则此时左子树的节点数目与右子树的节点数目也一定为奇数。

当 n 是奇数时，n 个结点的真二叉树满足左子树和右子树的结点数都是奇数，此时左子树和右子树的结点数之和是 n−1，假设左子树的数目为 i，则左子树的节点数目则为 n−1−i，则可以推出左子树与右子树的节点数目序列为：

假设我们分别构节点数目为 i 和节点数目为 n−1−i 的真二叉树，即可构造出 n 个结点的真二叉树。我们可以利用分治来构造真二叉树，分治的终止条件是 n=1。

当 n=1 时，此时只有一个结点的二叉树是真二叉树；
当 n>1 时，分别枚举左子树和右子树的根结点数，然后递归地构造左子树和右子树，并返回左子树与右子树的根节点列表。确定左子树与右子树的根节点列表后，分别枚举不同的左子树的根节点与右子树的根节点，从而可以构造出真二叉树的根节点。

1.2 代码

public List<TreeNode> allPossibleFBT(int n) {
        List<TreeNode> fullBinaryTrees = new ArrayList<TreeNode>();
        if (n % 2 == 0) {
            return fullBinaryTrees;
        }
        if (n == 1) {
            fullBinaryTrees.add(new TreeNode(0));
            return fullBinaryTrees;
        }
        for (int i = 1; i < n; i += 2) {
            List<TreeNode> leftSubtrees = allPossibleFBT(i);
            List<TreeNode> rightSubtrees = allPossibleFBT(n - 1 - i);
            for (TreeNode leftSubtree : leftSubtrees) {
                for (TreeNode rightSubtree : rightSubtrees) {
                    TreeNode root = new TreeNode(0, leftSubtree, rightSubtree);
                    fullBinaryTrees.add(root);
                }
            }
        }
        return fullBinaryTrees;
    }

2. 动态规划

2.1 算法与思路

上述同样的解题思路，我们还可以使用自底向上的动态规划。我们可以先构造节点数量为 1 的子树，然后构造节点数量为 5 的子树，然后依次累加即可构造出含有节点数目为 n 的真二叉树。

节点数目序列分别为 [(1,1)] 的子树可以构造出节点数目 3 的子树；
节点数目序列分别为 [(1,3),(3,1)] 的子树可以构造出节点数目 5 的真二叉树；
节点数目序列分别为 [(1,5),(3,3),(5,1)] 的子树可以构造出节点数目 7 的真二叉树；
节点数目序列分别为 [(1,i−2),(3,i−4),⋯ ,(i−2,1)] 的子树可以构造出节点数目 i 的真二叉树；

如果构造节点数目为 n 真二叉树，此时可以从节点数目序列为 [(1,n−2),(3,n−5),⋯ ,(n−2,1)] 的真二叉树中构成，按照所有可能的组合数进行枚举，即可构造成节点数目为 n 的真二叉树。

2.2 代码

public List<TreeNode> allPossibleFBT(int n) {
        List<TreeNode> fullBinaryTrees = new ArrayList<TreeNode>();
        if (n % 2 == 0) {
            return fullBinaryTrees;
        }
        if (n == 1) {
            fullBinaryTrees.add(new TreeNode(0));
            return fullBinaryTrees;
        }
        for (int i = 1; i < n; i += 2) {
            List<TreeNode> leftSubtrees = allPossibleFBT(i);
            List<TreeNode> rightSubtrees = allPossibleFBT(n - 1 - i);
            for (TreeNode leftSubtree : leftSubtrees) {
                for (TreeNode rightSubtree : rightSubtrees) {
                    TreeNode root = new TreeNode(0, leftSubtree, rightSubtree);
                    fullBinaryTrees.add(root);
                }
            }
        }
        return fullBinaryTrees;
    }