专栏首页曌的晓痴LeetCode - 所有可能的满二叉树

LeetCode - 所有可能的满二叉树

LeetCode第894题,难度中等。又是一题突然的100%,虽然并没有达到0ms的地步。

原题地址:https://leetcode-cn.com/problems/all-possible-full-binary-trees/

题目描述

满二叉树是一类二叉树,其中每个结点恰好有 0 或 2 个子结点。

返回包含 N 个结点的所有可能满二叉树的列表。答案的每个元素都是一个可能树的根结点。

答案中每个树的每个结点都必须有 node.val=0。

你可以按任何顺序返回树的最终列表。

示例:

输入: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]]

解释:

提示:

  1. 1 <= N <= 20

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/all-possible-full-binary-trees

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

这题中,我们需要首先搞清楚满二叉树的定义,然后熟练的运用到递归的方式。

这题的解法和之前的求所有子集很像,都是一开始先获取到最小的满二叉树,然后再在这颗满二叉树上面,添加父节点。使得这个树再次满足满二叉树的要求。

由于N为偶数时,不可能有符合要求的满二叉树,所有首先判断N是否是偶数。具体为什么N为偶数时没有满二叉树,各位自己画个图就知道了。

然后如果N为1,那么很明显只有一个节点。

否则的话,就从1到N,每次递加2的方式,分别获取i为3,5....19的情况下的满二叉树子树。当i为3时,左子树节点数量就是3,右子树节点数量就是N-3。分别获取到左右子树后,为左右子树新增一个父节点,然后将该父节点放入当前的List结果集中。

当N为19时,会去分别获取17,15,13....3,1的子树,最后将其组装在一起形成满足条件的满二叉树。

中文官网题解:

https://leetcode-cn.com/problems/all-possible-full-binary-trees/solution/

个人题解:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> allPossibleFBT(int N) {
        if (N % 2 == 0) {
            return new ArrayList<>(0);
        }
        List<TreeNode> list = new ArrayList<>();
        if (N == 1) {
            list.add(new TreeNode(0));
            return list;
        }
        N--;
        for (int i = 1; i < N; i += 2) {
            List<TreeNode> left = allPossibleFBT(i);
            List<TreeNode> right = allPossibleFBT(N - i);
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode node = new TreeNode(0);
                    node.left = l;
                    node.right = r;
                    list.add(node);
                }
            }
        }
        return list;
    }
}

结果:

小有实力的选手,居然又是超过了100%。

本文分享自微信公众号 - 曌的晓痴(gh_543795945efe),作者:zxyAnkh

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode - 最大二叉树

    原题地址:https://leetcode-cn.com/problems/maximum-binary-tree/

    晓痴
  • LeetCode - 先序遍历构造二叉树

    原题地址:https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder...

    晓痴
  • LeetCode - 翻转二叉树

    题目描述: ...

    晓痴
  • 零售业春天来了?四种方法带你提升线上销量

    人工智能、机器学习和深度学习的发展改变了我们的生活。尽管有时人们还没有意识到,但实际上早已融入日常生活中:人工智能优化谷歌的搜索结果、亚马逊推荐的“猜你喜欢”,...

    达观数据
  • Python的list()函数

    原文链接:https://www.runoob.com/python/att-list-list.html

    于小勇
  • Python列表常见操作和注意

    py3study
  • Python3 基本数据结构总结

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    chaibubble
  • 爱情36技之一劳永逸

    今天雅兴又起,再续爱情36技。大概率你们已经淡忘了 Java 那小子与 Python 菇凉浪漫的爱情故事,容我再帮着给大家回味一下。

    一猿小讲
  • 使用postman的pre-request script实现自动填充请求头部的功能

    我有一个需求,每次向SAP Cloud for Customer发送HTTP get请求时,需要自动填充自定义头部字段的值为当年时间戳,这个功能可以通过在htt...

    Jerry Wang
  • AS3程序员小福利--as3js介绍及FlashDevelop工程的配置

    本文作者:IMWeb 黄龙 原文出处:IMWeb社区 未经同意,禁止转载 ? 什么是AS3JS? AS3JS是ActionScript 3.0到Jav...

    IMWeb前端团队

扫码关注云+社区

领取腾讯云代金券