Leetcode: All Possible Full Binary Trees

All Possible Full Binary Trees



Similar Problems:


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:

fivetrees.png

Note:

  • 1 <= N <= 20

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution: Recursive
// Blog link: https://code.dennyzhang.com/all-possible-full-binary-trees
// Basic Ideas: Recursive
// If n is even, return nil
//
// Complexity: Time O(2^n), Space O(2^n)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var m map[int][]*TreeNode

func allPossibleFBT(N int) []*TreeNode {
    if N%2 == 0 { return []*TreeNode{} }
        if len(m) == 0 {
                m = map[int][]*TreeNode{}
        }
    v, ok := m[N]
    if ok { return v }

    if N == 1 {
        m[N] = []*TreeNode{&TreeNode{0, nil, nil}}
        return m[N]
    }

    res := []*TreeNode{}
    for i:= 1; i < N; i += 2 {
        l1, l2 := allPossibleFBT(i), allPossibleFBT(N-1-i)
        for _, p := range l1 {
            for _, q := range l2 {
                res = append(res, &TreeNode{0, p, q})
            }
        }
    }
    return res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.