I like to read this solution as a small machine: keep the useful information, throw away the noise. For 894. All Possible Full Binary Trees, the solution in this repository is mainly a two pointers solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are allPossibleFBT.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02A full binary tree is a binary tree where each node has exactly 0 or 2 children.
03
04Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree.
05
06Each node of each tree in the answer must have node.val = 0.
07
08You may return the final list of trees in any order.
09
10Input: 7
11Output: [[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]]
12Explanation:
13Note:
14
151 <= N <= 20
16**/
17
18/**
19 * Definition for a binary tree node.
20 * struct TreeNode {
21 * int val;
22 * TreeNode *left;
23 * TreeNode *right;
24 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
25 * };
26 */
27
28//Your runtime beats 36.47 % of cpp submissions.
29class Solution {
30public:
31 vector<TreeNode*> allPossibleFBT(int N) {
32 if(N==1){
33 vector<TreeNode*> ans;
34 TreeNode* node = new TreeNode(0);
35 ans.push_back(node);
36 return ans;
37 }else if(N%2==0){
38 vector<TreeNode*> ans;
39 return ans;
40 }else{
41 vector<TreeNode*> ans;
42
43 for(int lnum=1; lnum<=N-1-1; lnum+=2){
44 int rnum = N-1-lnum;
45 vector<TreeNode*> ltree = allPossibleFBT(lnum);
46 vector<TreeNode*> rtree = allPossibleFBT(rnum);
47 for(int ltreeix = 0; ltreeix < ltree.size(); ltreeix++){
48 for(int rtreeix = 0; rtreeix < rtree.size(); rtreeix++){
49 TreeNode* node = new TreeNode(0);
50 node->left = ltree[ltreeix];
51 node->right = rtree[rtreeix];
52 ans.push_back(node);
53 }
54 }
55 }
56 return ans;
57 }
58 }
59};
60
61/**
62Approach 1: Recursion
63Intuition and Algorithm
64
65Let \text{FBT}(N)FBT(N) be the list of all possible full binary trees with NN nodes.
66
67Every full binary tree TT with 3 or more nodes, has 2 children at its root. Each of those children left and right are themselves full binary trees.
68
69Thus, for N \geq 3N≥3, we can formulate the recursion: \text{FBT}(N) =FBT(N)= [All trees with left child from \text{FBT}(x)FBT(x) and right child from \text{FBT}(N-1-x)FBT(N−1−x), for all xx].
70
71Also, by a simple counting argument, there are no full binary trees with a positive, even number of nodes.
72
73Finally, we should cache previous results of the function \text{FBT}FBT so that we don't have to recalculate them in our recursion.
74**/
75
76//Your runtime beats 36.47 % of cpp submissions.
77/**
78 * Definition for a binary tree node.
79 * struct TreeNode {
80 * int val;
81 * TreeNode *left;
82 * TreeNode *right;
83 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
84 * };
85 */
86class Solution {
87public:
88 map<int, vector<TreeNode*> > size2tree;
89
90 vector<TreeNode*> allPossibleFBT(int N) {
91 if(size2tree.find(N)!=size2tree.end()){
92 return size2tree.at(N);
93 }else{
94 vector<TreeNode*> ans;
95 if(N==1){
96 TreeNode* node = new TreeNode(0);
97 ans.push_back(node);
98 }else if(N%2==1){
99 for(int lnum=1; lnum<=N-1-1; lnum+=2){
100 int rnum = N-1-lnum;
101 vector<TreeNode*> ltree = allPossibleFBT(lnum);
102 vector<TreeNode*> rtree = allPossibleFBT(rnum);
103 for(int ltreeix = 0; ltreeix < ltree.size(); ltreeix++){
104 for(int rtreeix = 0; rtreeix < rtree.size(); rtreeix++){
105 TreeNode* node = new TreeNode(0);
106 node->left = ltree[ltreeix];
107 node->right = rtree[rtreeix];
108 ans.push_back(node);
109 }
110 }
111 }
112 }
113 size2tree.insert(make_pair(N, ans));
114 return ans;
115 }
116 }
117};
118
119/**
120Complexity Analysis
121
122Time Complexity: O(2^N). For odd N, let N = 2k + 1. Then, |FBT(N)| = C_k
123, the k-th catalan number; and \sum\limits_{k < N/2}C_
124 (the complexity involved in computing intermediate results required) is bounded by O(2^N).
125However, the proof is beyond the scope of this article.
126
127Space Complexity: O(2^N).
128**/Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.