标签搜索

目 录CONTENT

文章目录

【算法模板】满二叉树生成

陈铭
2022-11-16 / 0 评论 / 2 点赞 / 295 阅读 / 373 字 / 正在检测是否收录...

例题:所有可能的真二叉树

力扣面试题 894题为例:

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

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

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


image

    Map<Integer, List<TreeNode>> memo = new HashMap();
    public List<TreeNode> allPossibleFBT_leetcode(int N) {
        if (!memo.containsKey(N)) {
            List<TreeNode> ans = new LinkedList();
            // 满二叉树的节点数量都是奇数
            if (N == 1) {
                ans.add(new TreeNode(0));
            } else if (N % 2 == 1) {
                for (int x = 0; x < N; ++x) {
                    // 某个节点下的左右子树节点数量==N-1
                    // 左子树节点数为x,右子树节点数为y,x和y都应该是奇数
                    // 因此else if (N % 2 == 1)是为了避免allPossibleFBT(x)、allPossibleFBT(y)出现错误的结果
                    // 即当x、y为偶数时,返回的List<TreeNode>,其大小为0,那么会进入下个循环
                    int y = N - 1 - x;
                    for (TreeNode left : allPossibleFBT(x)) {
                        for (TreeNode right : allPossibleFBT(y)) {
                            TreeNode bns = new TreeNode(0);
                            bns.left = left;
                            bns.right = right;
                            ans.add(bns);
                        }
                    }
                }
            }
            memo.put(N, ans);
        }
        // memo缓存数量为N的满二叉树,避免再次递归,节约时间
        return memo.get(N);
    }
2

评论区