Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/894.html

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

Companies:
Google

Related Topics:
Tree, Recursion

Solution 1.

  • /**
     * 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) {
            if (N % 2 == 0)
                return new ArrayList<TreeNode>();
            Map<Integer, List<TreeNode>> map = new HashMap<Integer, List<TreeNode>>();
            List<TreeNode> oneList = new ArrayList<TreeNode>();
            oneList.add(new TreeNode(0));
            map.put(1, oneList);
            for (int i = 3; i <= N; i += 2) {
                List<TreeNode> curList = map.getOrDefault(i, new ArrayList<TreeNode>());
                int sum = i - 1;
                for (int left = 1; left < sum; left++) {
                    int right = sum - left;
                    List<TreeNode> leftList = map.getOrDefault(left, new ArrayList<TreeNode>());
                    List<TreeNode> rightList = map.getOrDefault(right, new ArrayList<TreeNode>());
                    for (TreeNode leftNode : leftList) {
                        for (TreeNode rightNode : rightList) {
                            TreeNode root = new TreeNode(0);
                            root.left = leftNode;
                            root.right = rightNode;
                            curList.add(root);
                        }
                    }
                }
                map.put(i, curList);
            }
            return map.get(N);
        }
    }
    
    ############
    
    /**
     * 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 {
        private List<TreeNode>[] f = new List[21];
    
        public List<TreeNode> allPossibleFBT(int n) {
            return dfs(n);
        }
    
        private List<TreeNode> dfs(int n) {
            if (f[n] != null) {
                return f[n];
            }
            if (n == 1) {
                return Collections.singletonList(new TreeNode());
            }
            List<TreeNode> res = new ArrayList<>();
            for (int i = 0; i < n - 1; ++i) {
                int j = n - i - 1;
                for (TreeNode left : dfs(i)) {
                    for (TreeNode right : dfs(j)) {
                        res.add(new TreeNode(0, left, right));
                    }
                }
            }
            f[n] = res;
            return res;
        }
    }
    
  • // OJ: https://leetcode.com/problems/all-possible-full-binary-trees/
    // Time: O(2^N)
    // Space: O(2^N)
    class Solution {
    public:
        vector<TreeNode*> allPossibleFBT(int N) {
            if (N % 2 == 0) return {};
            if (N == 1) return { new TreeNode(0) };
            vector<TreeNode*> ans;
            for (int i = 1; i <= N - 2; i += 2) {
                auto lefts = allPossibleFBT(i);
                auto rights = allPossibleFBT(N - i - 1);
                for (auto left : lefts) {
                    for (auto right : rights) {
                        auto root = new TreeNode(0);
                        root->left = left;
                        root->right = right;
                        ans.push_back(root);
                    }
                }
            }
            return ans;
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
            @cache
            def dfs(n):
                if n == 1:
                    return [TreeNode()]
                res = []
                if n % 2:
                    for i in range(n - 1):
                        j = n - i - 1
                        for left in dfs(i):
                            for right in dfs(j):
                                res.append(TreeNode(0, left, right))
                return res
    
            return dfs(n)
    
    ############
    
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def allPossibleFBT(self, N):
            """
            :type N: int
            :rtype: List[TreeNode]
            """
            N -= 1
            if N == 0: return [TreeNode(0)]
            res = []
            for l in range(1, N, 2):
                for left in self.allPossibleFBT(l):
                    for right in self.allPossibleFBT(N - l):
                        node = TreeNode(0)
                        node.left = left
                        node.right = right
                        res.append(node)
            return res
    
  • /**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func allPossibleFBT(n int) []*TreeNode {
    	f := map[int][]*TreeNode{}
    	var dfs func(n int) []*TreeNode
    	dfs = func(n int) []*TreeNode {
    		if v, ok := f[n]; ok {
    			return v
    		}
    		if n == 1 {
    			return []*TreeNode{&TreeNode{Val: 0} }
    		}
    		res := []*TreeNode{}
    		for i := 0; i < n-1; i++ {
    			j := n - i - 1
    			for _, left := range dfs(i) {
    				for _, right := range dfs(j) {
    					res = append(res, &TreeNode{0, left, right})
    				}
    			}
    		}
    		f[n] = res
    		return res
    	}
    	return dfs(n)
    }
    
  • /**
     * Definition for a binary tree node.
     * class TreeNode {
     *     val: number
     *     left: TreeNode | null
     *     right: TreeNode | null
     *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
     *         this.val = (val===undefined ? 0 : val)
     *         this.left = (left===undefined ? null : left)
     *         this.right = (right===undefined ? null : right)
     *     }
     * }
     */
    
    function allPossibleFBT(n: number): Array<TreeNode | null> {
        const f: Array<Array<TreeNode | null>> = new Array(n + 1)
            .fill(0)
            .map(() => []);
        const dfs = (n: number): Array<TreeNode | null> => {
            if (f[n].length) {
                return f[n];
            }
            if (n === 1) {
                f[n].push(new TreeNode(0));
                return f[n];
            }
            const ans: Array<TreeNode | null> = [];
            for (let i = 0; i < n - 1; ++i) {
                const j = n - 1 - i;
                for (const left of dfs(i)) {
                    for (const right of dfs(j)) {
                        ans.push(new TreeNode(0, left, right));
                    }
                }
            }
            return (f[n] = ans);
        };
        return dfs(n);
    }
    
    
  • // Definition for a binary tree node.
    // #[derive(Debug, PartialEq, Eq)]
    // pub struct TreeNode {
    //   pub val: i32,
    //   pub left: Option<Rc<RefCell<TreeNode>>>,
    //   pub right: Option<Rc<RefCell<TreeNode>>>,
    // }
    //
    // impl TreeNode {
    //   #[inline]
    //   pub fn new(val: i32) -> Self {
    //     TreeNode {
    //       val,
    //       left: None,
    //       right: None
    //     }
    //   }
    // }
    
    impl TreeNode {
        pub fn new_with_node(left: Option<Rc<RefCell<TreeNode>>>, right: Option<Rc<RefCell<TreeNode>>>) -> Self {
            Self {
                val: 0,
                left,
                right,
            }
        }
    }
    
    use std::rc::Rc;
    use std::cell::RefCell;
    impl Solution {
        #[allow(dead_code)]
        pub fn all_possible_fbt(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
            let mut record_vec = vec![vec![]; n as usize + 1];
            Self::dfs(n, &mut record_vec)
        }
    
        #[allow(dead_code)]
        fn dfs(n: i32, record_vec: &mut Vec<Vec<Option<Rc<RefCell<TreeNode>>>>>) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
            if record_vec[n as usize].len() != 0 {
                return record_vec[n as usize].clone();
            }
            if n == 1 {
                // Just directly return a single node
                return vec![Some(Rc::new(RefCell::new(TreeNode::new(0))))];
            }
            // Otherwise, need to construct return vector
            let mut ret_vec = Vec::new();
    
            // Enumerate the node number for left subtree from 0 -> n - 1
            for i in 0..n - 1 {
                // The number of right subtree node
                let j = n - i - 1;
                for left in Self::dfs(i, record_vec) {
                    for right in Self::dfs(j, record_vec) {
                        // Construct the ret vector
                        ret_vec.push(Some(Rc::new(RefCell::new(TreeNode::new_with_node(left.clone(), right.clone())))));
                    }
                }
            }
    
            record_vec[n as usize] = ret_vec;
    
            record_vec[n as usize].clone()
        }
    }
    

All Problems

All Solutions