leetcode讲解--894. All Possible Full Binary Trees

题目A full binary tree is a binary tree where each node has exactly 0 or 2 children.Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree.Each node of each tree in the answer must have node.val = 0.You may return the final list of trees in any order.Example 1:Input: 7Output: [[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]]Explanation:Note:1 <= N <= 20题目地址讲解这道题太适合用来训练递归了。与以前做过的题不同，这里的返回值是一个list。而且还需要对树比较了解。最好是先画出N=1到5的时候，树的结构，然后会发现一些规律。注意下i+=2，步长是2。Java代码/** * 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) { List<TreeNode> result = new ArrayList<>(); if(N%2==0){ return result; } if(N==1){ result.add(new TreeNode(0)); return result; } for(int i=1;i<N;i+=2){ for(TreeNode l:allPossibleFBT(i)){ for(TreeNode r:allPossibleFBT(N-1-i)){ TreeNode root = new TreeNode(0); root.left = l; root.right = r; result.add(root); } } } return result; }}