当前位置:   article > 正文

894. 所有可能的满二叉树_[894]所有可能的满二叉树

[894]所有可能的满二叉树

题目来源

894. 所有可能的满二叉树

题目描述

在这里插入图片描述

题目解析

递归

Java 首先偶数是不能构成满二叉树的。 思路是把总node数分别左边,根,右边进行递归,如7个node可以分成1,1,5;3,1,5;5,1,1(左,根,右)。 5个node又可以分为1,1,3和3,1,1。 3个node又可以分为1,1,1。 1个node直接返回。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 public static  List<TreeNode> allPossibleFBT(int N) {
        List<TreeNode > list = new LinkedList<>();
        if (N % 2 == 0){
            return list;
        }

        if (N == 1){
            list.add(new TreeNode(0));
            return list;
        }

        for (int i = 1; i < N; i += 2){
            List<TreeNode> ll = allPossibleFBT(i);
            List<TreeNode> rl = allPossibleFBT(N - 1 - i);
            for (TreeNode l : ll){
                for (TreeNode r : rl){
                    TreeNode root = new TreeNode(0);
                    root.left = l;
                    root.right = r;
                    list.add(root);
                }
            }
        }

        return list;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/783418
推荐阅读
相关标签
  

闽ICP备14008679号