赞
踩
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; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。