LeetCode - Medium - 894. All Possible Full Binary Trees

逃离我推掉我的手 2022-10-07 15:55 97阅读 0赞

## Topic ##

*  Tree
 *  Recursion

## Description ##

[https://leetcode.com/problems/all-possible-full-binary-trees/][https_leetcode.com_problems_all-possible-full-binary-trees]

Given an integer n, return a list of all possible **full binary trees** with `n` nodes. Each node of each tree in the answer must have `Node.val == 0`.

Each element of the answer is the root node of one possible tree. You may return the final list of trees in **any order**.

A **full binary tree** is a binary tree where each node has exactly `0` or `2` children.

**Example 1:**  
![0f705d3d89cf725147e181feb2b5b096.png][]

Input: n = 7
    Output: [[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]]

**Example 2:**

Input: n = 3
    Output: [[0,0,0]]

**Constraints:**

*  `1 <= n <= 20`

## Analysis ##

受[LeetCode - Medium - 95. Unique Binary Search Trees II][]启发。

方法一：递归版

方法二：迭代版

## Submission ##

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.TreeMap;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class AllPossibleFullBinaryTrees { 
    	
    	//方法一：递归版
        public List<TreeNode> allPossibleFBT(int n) { 
            List<TreeNode> result = new ArrayList<>();
            
            if((n & 1) == 0) return result; //偶数的直接返回
            
            if(n == 1) { 
            	result.add(new TreeNode(0));
            	return result;
            }
            
            for(int i = 1; i < n; i += 2) { 
            	
            	List<TreeNode> lefts = allPossibleFBT(i);
            	List<TreeNode> rights = allPossibleFBT(n - i - 1);
            	
            	for(TreeNode left : lefts) { 
            		for(TreeNode right : rights) { 
            			TreeNode node = new TreeNode(0);
            			
            			node.left = left;
            			node.right = right;
            			
            			result.add(node);
            		}
            	}
            }	
            return result;
        }
        
        //方法二：迭代版
        public List<TreeNode> allPossibleFBT2(int n) { 
            List<TreeNode> result = new ArrayList<>();
            if((n & 1) == 0) return result; //偶数的直接返回
    
            Map<Integer, List<TreeNode>> cache = new HashMap<>();
            
            cache.put(1, Arrays.asList(new TreeNode(0)));
            
            
            for(int i = 3; i <= n; i += 2) { 
            	
            	List<TreeNode> tempList = new ArrayList<>();
            	for(int j = 1; j < i; j += 2) { 
            		
            		List<TreeNode> lefts = cache.get(j);
            		List<TreeNode> rights = cache.get(i - j - 1);
            		
            		for(TreeNode left : lefts) { 
            			for(TreeNode right : rights) { 
            				TreeNode node = new TreeNode(0);
            				
            				node.left = i == n ? clone(left) : left;
            				node.right = i == n ? clone(right) : right;
            				
            				tempList.add(node);
            			}
            		}
            	}
            	if(i == n)
            		return tempList;
            	cache.put(i, tempList);
            }
            
            return cache.get(1);
        }
        
        private TreeNode clone(TreeNode node) { 
        	if(node == null) return null;
        	
        	TreeNode newNode = new TreeNode(node.val);
        	
        	newNode.left = clone(node.left);
        	newNode.right = clone(node.right);
        	
        	return newNode;
        }
        
        //下面求出符合题意n个节点二叉树的棵数
        
        public int count(int n) { 
        	
        	if((n & 1) == 0) return 0; 
        	
        	if(n == 1) return 1;
        	int result = 0;
        	for(int i = 1; i < n; i += 2) { 
        		
        		int l = count(i);
        		int r = count(n - i - 1);
        		
        		
        		result += (l * r);
        	}
        	return result;
        }
        
        public int count2(int n) {     	
        	if((n & 1) == 0) return 0; 
        	
        	Map<Integer, Integer> cache = new TreeMap<>();
        	cache.put(1, 1);
    
            for(int i = 3; i <= n; i += 2) { 
            	int count = 0;
            	for(int j = 1; j < i; j += 2) { 
            		
            		int l = cache.get(j);
            		int r = cache.get(i - j - 1);
            		
            		count += (l * r);
            	}
            	cache.put(i, count);
            }
            System.out.println(cache);
        	return cache.get(n);
        }
        
        
    }

## Test ##

import static org.junit.Assert.*;
    import static com.lun.util.BinaryTree.integers2BinaryTree;
    
    import java.util.List;
    
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class AllPossibleFullBinaryTreesTest { 
    
    	@Test
    	public void test() { 
    		AllPossibleFullBinaryTrees obj = new AllPossibleFullBinaryTrees();
    		List<TreeNode> actual = obj.allPossibleFBT(7);
    		TreeNode[] expected = { integers2BinaryTree(0,0,0,null,null,0,0,null,null,0,0)
    				,integers2BinaryTree(0,0,0,null,null,0,0,0,0)
    				,integers2BinaryTree(0,0,0,0,0,0,0)
    				,integers2BinaryTree(0,0,0,0,0,null,null,null,null,0,0)
    				,integers2BinaryTree(0,0,0,0,0,null,null,0,0)};
    		
    		int count = 0;
    		for(TreeNode a : actual) { 
    			for(TreeNode e : expected) { 
    				if(BinaryTree.equals(a, e))
    					count++;
    			}
    		}
    		
    		assertEquals(5, count);
    	}
    	
    	@Test
    	public void test2() { 
    		AllPossibleFullBinaryTrees obj = new AllPossibleFullBinaryTrees();
    		
    		List<TreeNode> actual = obj.allPossibleFBT2(7);
    		TreeNode[] expected = { integers2BinaryTree(0,0,0,null,null,0,0,null,null,0,0)
    				,integers2BinaryTree(0,0,0,null,null,0,0,0,0)
    				,integers2BinaryTree(0,0,0,0,0,0,0)
    				,integers2BinaryTree(0,0,0,0,0,null,null,null,null,0,0)
    				,integers2BinaryTree(0,0,0,0,0,null,null,0,0)};
    		
    		int count = 0;
    		for(TreeNode a : actual) { 
    			for(TreeNode e : expected) { 
    				if(BinaryTree.equals(a, e))
    					count++;
    			}
    		}
    		
    		assertEquals(5, count);
    	}
    	
    	@Test
    	public void testCount() { 
    		AllPossibleFullBinaryTrees obj = new AllPossibleFullBinaryTrees();
    		System.out.println(obj.count(35));//129644790
    		System.out.println(obj.count2(35));//129644790
    		//{1=1, 3=1, 5=2, 7=5, 9=14, 11=42, 13=132, 15=429, 17=1430, 19=4862, 21=16796, 
    		// 23=58786, 25=208012, 27=742900, 29=2674440, 31=9694845, 33=35357670, 35=129644790}
    	}
    }

[https_leetcode.com_problems_all-possible-full-binary-trees]: https://leetcode.com/problems/all-possible-full-binary-trees/
[0f705d3d89cf725147e181feb2b5b096.png]: /images/20221005/d83e229ebfe242e391d96a043e6ba141.png
[LeetCode - Medium - 95. Unique Binary Search Trees II]: https://blog.csdn.net/u011863024/article/details/117830258