Thursday, October 15, 2020

LeetCode [894] All Possible Full Binary Trees

 894. All Possible Full Binary Trees

Medium

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: 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]]
Explanation:

 

Note:

  • 1 <= N <= 20
 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  public TreeNode clone(TreeNode tree)  {
    if (null == tree)
    {
      return null;
    }
    
    TreeNode new_tree = new TreeNode(tree.val);
    new_tree.left = clone(tree.left);
    new_tree.right = clone(tree.right);
    return new_tree;
  }
  
  public List<TreeNode> allPossibleFBT(int N) {
    List<TreeNode> ret = new ArrayList<TreeNode>();
    if (1 == N) {
      ret.add(new TreeNode(0));
    } else if (N % 2 != 0) {
      for (int i = 2; i <= N; i += 2) {
        List<TreeNode> left_branch = allPossibleFBT(i - 1);
        List<TreeNode> right_branch = allPossibleFBT(N - i);
        for (Iterator<TreeNode> left_iter = left_branch.iterator(); left_iter.hasNext(); ) {
          TreeNode left = left_iter.next();
          for (Iterator<TreeNode> right_iter = right_branch.iterator(); right_iter.hasNext(); ) {
            TreeNode right = right_iter.next();
            
            TreeNode tree = new TreeNode(0);
            
            // If we're using the last right branch, then this will be the last time this left branch is used and can hence
            // be shallow copied, otherwise the tree will have to be cloned
            tree.left = right_iter.hasNext() ? clone(left) : left;
            
            // If we're using the last left branch, then this will be the last time this right branch is used and can hence
            // be shallow copied, otherwise the tree will have to be cloned
            tree.right = left_iter.hasNext() ? clone(right) : right;
            
            ret.add(tree);
          }
        }
      }
    }
    return ret;
  }
}
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)