# Tree
###### tags: `Study_aboard`
## Binary Tree Traversal
==看middle的位置在哪==
### Traversal
preorder : middle -> left -> right
inorder : left -> middle -> right (sorted array in BST)
postorder : left-> right ->middle
(watch out NULL nodes)
Preorder
```cpp
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if(!root){
return res;
}
res.push_back(root->val);
if(root->left){
vector<int> res_left;
res_left = preorderTraversal(root->left);
for(auto x:res_left){
res.push_back(x);
}
}
if(root->right){
vector<int> res_right;
res_right = preorderTraversal(root->right);
for(auto x:res_right){
res.push_back(x);
}
}
return res;
}
};
```
Postorder
```cpp
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if(!root){
return res;
}
if(root->left){
vector<int> res_left;
res_left = postorderTraversal(root->left);
for(auto x:res_left){
res.push_back(x);
}
}
if(root->right){
vector<int> res_right;
res_right = postorderTraversal(root->right);
for(auto x:res_right){
res.push_back(x);
}
}
res.push_back(root->val);
return res;
}
};
```
## Binary Tree Inorder Traversal
```cpp
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
if(root==nullptr) return res;
if(root->left!=nullptr) res = inorderTraversal(root->left);
res.push_back(root->val);
if(root->right!=nullptr) for(auto r:inorderTraversal(root->right)) res.push_back(r);
return res;
}
};
```
## Kth Smallest Element in a BST
Initial: No thoughs
Sol: ==Inorder traversal of BST will output a sorted array !!==
```cpp
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
return kthSmallestDFS(root, k);
}
int kthSmallestDFS(TreeNode* root, int &k) {
if (!root) return -1;
int val = kthSmallestDFS(root->left, k);
if (k == 0) return val;
if (--k == 0) return root->val;
return kthSmallestDFS(root->right, k);
}
};
```
## Symmetric Tree
```cpp
class Solution {
public:
bool isSymmetric(TreeNode *root) {
if (!root) return true;
return helper(root->left, root->right);
}
bool helper(TreeNode* p, TreeNode* q) {
if (!p && !q) { // p is Null && q is Null
return true;
}
else if (!p || !q) { // one of p or q is Null
return false;
}
if (p->val != q->val) {
return false;
}
return helper(p->left,q->right) && helper(p->right, q->left); // require left and right to be true at the same time
}
};
```
## Same Tree
easy
```cpp
bool isSameTree(TreeNode *p, TreeNode *q) {
if (p == NULL || q == NULL) return (p == q);
return (p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right));
}
```
## Maximum Depth of Binary tree
1. DFS
```cpp
class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
};
```
2. BFS (with levels recording)
```cpp
class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
int res = 0;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
++res;
for (int i = q.size(); i > 0; --i) {
TreeNode *t = q.front(); q.pop();
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
}
return res;
}
};
```
## Balanced binary tree
Initial : start from root, get the height of left and right subtree, and then do again for every node.
Problem: Will calculate the same thing many times
Solution: Use recursion to implement the whole thing from end to top
[back to back swe](https://www.youtube.com/watch?v=LU4fGD-fgJQ&list=PLiQ766zSC5jND9vxch5-zT7GuMigiWaV_&index=8)
```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isBalanced(TreeNode* root) {
return height(root)==-1?false:true;
}
int height(TreeNode* root){
if(root==nullptr){
return 0;
}
int r = height(root->right);
int l = height(root->left);
if(r==-1 || l==-1) return -1;// not balanced
if(abs(r-l)<=1) return max(r,l)+1;// balanced
else return -1;// -1 means not balanced
}
};
```
time complexity O(N) N is the node number
space complexity O(h) h is the height of the tree
## Count complete tree nodes
Initial: use queue to bfs and count the nodes
Problem: slow
Solution: utilize a ==complete== tree
Initial sol (recursion)
```cpp
class Solution {
public:
int countNodes(TreeNode* root) {
return root ? (1 + countNodes(root->left) + countNodes(root->right)) : 0;
}
};
```
Initial sol (iterative)
```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int countNodes(TreeNode* root) {
int res = 0;
queue <TreeNode*> q;
if(!root) return 0;
if(!root->left && !root->right) return 1;
q.push(root);
while(!q.empty()){
TreeNode* cur = q.front();
q.pop();
res++;
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
return res;
}
};
```
Faster : check left level and right level, if they are the same, the tree is full, otherwise count it same as the original version.
```cpp
class Solution {
public:
int countNodes(TreeNode* root) {
int hLeft = 0, hRight = 0;
TreeNode *pLeft = root, *pRight = root;
while (pLeft) {
++hLeft;
pLeft = pLeft->left;
}
while (pRight) {
++hRight;
pRight = pRight->right;
}
if (hLeft == hRight) return pow(2, hLeft) - 1;
return countNodes(root->left) + countNodes(root->right) + 1;
}
};
```
## Serilaize and Deserialize Binary Tree
not hard
```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res;
queue <TreeNode*> q;
if(!root) return res;
q.push(root);
while(!q.empty()){
TreeNode* cur = q.front();
q.pop();
if(cur){
res += to_string(cur->val)+" ";
q.push(cur->left);
q.push(cur->right);
}
else{
res=res+"# ";
}
}
return res;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data.empty()) {
return NULL;
}
istringstream iss (data);
string x;
queue<TreeNode*> q;
iss >> x;
TreeNode* root = new TreeNode(stoi(x));
q.push(root);
//it is the same as bfs
while (iss >> x) {
TreeNode *cur = q.front();
q.pop();
//the x is already generated in while condition
cur->left = x == "#" ? NULL : new TreeNode(stoi(x));
iss >> x;
cur->right = x == "#" ? NULL : new TreeNode(stoi(x));
//same here, we no longer need to put null ptr into the queue, because it do not need to find its child
if (cur->left) {
q.push(cur->left);
}
if (cur->right) {
q.push(cur->right);
}
}
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
```
## All nodes Distance K in Binary tree
Initial: construct parent pointer, and then bfs to get distance K nodes
```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
if (!root) return {};
vector<int> res;
unordered_map<TreeNode*, TreeNode*> parent;
parent[root]=nullptr;
unordered_set<TreeNode*> visited; // for bfs
findParent(root, parent);
helper(target, K, parent, visited, res);
return res;
}
void findParent(TreeNode* node, unordered_map<TreeNode*, TreeNode*>& parent) {
if(node->left!=nullptr){
parent[node->left]=node;
findParent(node->left, parent);
}
if(node->right!=nullptr){
parent[node->right]=node;
findParent(node->right, parent);
}
}
void helper(TreeNode* node, int K, unordered_map<TreeNode*, TreeNode*>& parent, unordered_set<TreeNode*>& visited, vector<int>& res) {
if (visited.count(node)) return; // bfs no repeated visit
visited.insert(node);
if (K == 0) {res.push_back(node->val); return;}
if (node->left) helper(node->left, K - 1, parent, visited, res);
if (node->right) helper(node->right, K - 1, parent, visited, res);
if (parent[node]) helper(parent[node], K - 1, parent, visited, res);
}
};
```
Complexities
n = total amount of nodes in the binary tree
m = total edges
Time: O( n + m )
This is standard to Breadth First Search. We upper bound the time by the number of nodes we can visit and edges we can traverse (at maximum).
Space: O( n )
We have a hashtable upper bounded by n mappings, a mapping to each node's parent.
[back to back swe](https://www.youtube.com/watch?v=nPtARJ2cYrg&list=PLiQ766zSC5jND9vxch5-zT7GuMigiWaV_&index=5)
## Invert Binary Tree
1. recursive
```cpp
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root) {
std::swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
}
return root;
}
};
```
2. iteration
utilize stack or queue to iterate all nodes
```cpp
TreeNode* invertTree(TreeNode* root) {
std::stack<TreeNode*> stk; // stack First In Last out
stk.push(root);
while (!stk.empty()) {
TreeNode* p = stk.top();
stk.pop();
if (p) { // if p is not NULL
stk.push(p->left);
stk.push(p->right);
std::swap(p->left, p->right);
}
}
return root;
}
```
## Binary tree level order traversal ==Amazon==
good problem
Initial: bfs by queue, 將每層用nullptr補滿以作為分隔
Problem: TLE
```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue <TreeNode*> q;
q.push(root);
int level=0;
vector<TreeNode*> level_tree;
vector<int> level_res;
vector<vector<int>> res;
while(!q.empty()){
TreeNode* cur = q.front();
q.pop();
level_tree.push_back(cur);
if(level_tree.size()==pow(2,level)){
for(auto tree: level_tree){
if(tree!=nullptr) level_res.push_back(tree->val);
}
if(level_res.size()==0) break;
res.push_back(level_res);
level++;
level_res.clear();
level_tree.clear();
}
if(cur!=nullptr){
q.push(cur->left);
q.push(cur->right);
}
else{
q.push(nullptr);
q.push(nullptr);
}
}
return res;
}
};
```
Solution: use two queue front and back to seperate each level
BFS level -> ==use two queues to seperate!!==
```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue <TreeNode*> front, back;
vector<int> temp_res;
vector<vector<int>> res;
if(root==nullptr) return res;
front.push(root);
while(!front.empty() || !back.empty()){
TreeNode* cur = front.front();
front.pop();
temp_res.push_back(cur->val);
if(cur->left!=nullptr) back.push(cur->left);
if(cur->right!=nullptr) back.push(cur->right);
if(front.empty()){
front=back;
while (!back.empty()) back.pop(); // clear back queue
res.push_back(temp_res);
temp_res.clear();
}
}
return res;
}
};
```
## Binary Tree vertical order traversal
Sol:
通過樹上節點的相對位置，我們可以對樹節點進行編號，左節點的列編號值是當前節點的列編號減一，右節點的列編號是當前節點的列編號加一。通過一次深度優先或寬度優先遍曆，就可以得到這些節點的列編號。
如果用DFS遍歷將列編號按遍歷順序加入答案結果，可能會導致，同一列的陣列中節點的編號沒有按照節點深度排序。所以採用BFS更優秀，可以按深度將同一列節點按順序加入陣列。(參考下圖)
```cpp
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: the root of tree
* @return: the vertical order traversal
*/
vector<vector<int>> verticalOrder(TreeNode * root) {
map<int, vector<int>> results; // map that records int=order, vector=tree node val in the order
queue<pair<TreeNode *, int>> q; // queue that records the order and the tree nodes
q.push({root, 0});
// 宽度优先遍历，同时记录列编号
while (! q.empty()) {
pair<TreeNode *, int> nodePair = q.front();
q.pop();
TreeNode * node = nodePair.first;
int colIdx = nodePair.second;
if (node != NULL) {
results[colIdx].push_back(node -> val);
q.push({node -> left, colIdx - 1});
q.push({node -> right, colIdx + 1});
}
}
vector<vector<int>> result;
for (pair<int, vector<int>> resultPair: results) {
result.push_back(resultPair.second);
}
return result;
}
};
```
## Binary Tree Paths
```cpp
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
recursive(root,"",res);
return res;
}
void recursive(TreeNode* root, string str,vector<string>& res){
if(root->left){
recursive(root->left,str+to_string(root->val)+"->",res);
}
if(root->right){
recursive(root->right,str+to_string(root->val)+"->",res);
}
if(!root->right && !root->left){
str += to_string(root->val);
res.push_back(str);
}
}
};
```
## Path Sum
```cpp
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum)
{
if (!root) return false;
if (!root->left && !root->right) return root->val == sum;
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
};
```
## Path Sum II
solution 1.
```cpp
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> res = helper(root,targetSum);
vector<vector<int>> ans;
for(int i=0;i<res.size();i++){
int sum=0;
for(int j=0;j<res[i].size();j++){
sum += res[i][j];
}
if(sum==targetSum && res[i][0]==root->val && res[i].size()>1){
ans.push_back(res[i]);
}
}
return ans;
}
vector<vector<int>> helper(TreeNode* root, int targetSum) {
vector<vector<int>> left_path, right_path;
if(!root){
return left_path;
}
if(root->left != NULL){
left_path = helper(root->left,targetSum);
for(int i=0;i<left_path.size();i++){
int sum = 0;
for(int j=0; j<left_path[i].size();j++){
sum += left_path[i][j];
}
if(sum+root->val <= targetSum){
left_path[i].insert(left_path[i].begin(),root->val);
}
}
if(root->val <= targetSum){
vector <int> temp;
temp.push_back(root->val);
left_path.push_back(temp);
}
}
if(root->right!=NULL){
right_path = helper(root->right,targetSum);
for(int i=0;i<right_path.size();i++){
int sum = 0;
for(int j=0; j<right_path[i].size();j++){
sum += right_path[i][j];
}
if(sum+root->val <= targetSum){
right_path[i].insert(right_path[i].begin(),root->val);
}
}
if(root->val<= targetSum){
vector <int> temp;
temp.push_back(root->val);
right_path.push_back(temp);
}
}
if(!root->right && !root->left && root->val <= targetSum ){ // if node is leaf return itself
vector <int> temp;
temp.push_back(root->val);
//cout << root->val<<endl;
left_path.push_back(temp);
return left_path;
}
left_path.insert(left_path.end(), right_path.begin(), right_path.end());
return left_path;
}
};
```
solution 2.
==可以傳位置使得所有人共用==
```cpp
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int> > paths;
vector<int> path;
findPaths(root, sum, path, paths);
return paths;
}
private:
void findPaths(TreeNode* node, int sum, vector<int> path, vector<vector<int> >& paths) {
if (!node) return;
path.push_back(node -> val);
if (!(node -> left) && !(node -> right) && sum == node -> val)
paths.push_back(path);
findPaths(node -> left, sum - node -> val, path, paths);
findPaths(node -> right, sum - node -> val, path, paths);
return ;
}
};
```
## Minimum Depth of Binary Tree
```cpp
class Solution {
public:
int minDepth(TreeNode* root) {
if(!root) return 0;
if(!root->left) return 1 + minDepth(root->right);
if(!root->right) return 1 + minDepth(root->left);
return 1+min(minDepth(root->left),minDepth(root->right));
}
};
```
## Maximum Depth of Binary Tree
```cpp
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root){return 0;}
if(!root->left){return 1+maxDepth(root->right);}
if(!root->right){return 1+maxDepth(root->left);}
return 1+max(maxDepth(root->left),maxDepth(root->right));
}
};
```
## Lowest Common Ancestor of a Binary Tree
Initial: 將兩個node的所有root列出後，比較第一個相同的數字。
Problem: 但缺乏parent pointer，因此需用map自行建立，slow。
iterative solution
```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
map<TreeNode*, TreeNode*> parent; // map to record parents of both nodes
stack<TreeNode*> stk; // execute nodes
parent[root] = nullptr; // let root's parent is nullptr in the map
stk.push(root);
// implement parent pointer
while (parent.find(p) == parent.end() || parent.find(q)==parent.end()) // find==end means did not find in the map
{
TreeNode *node = stk.top();
stk.pop();
if (node->left != nullptr)
{
parent[node->left] = node;
stk.push(node->left);
}
if (node->right != nullptr)
{
parent[node->right] = node;
stk.push(node->right);
}
}
set<TreeNode*> ancestors;
while (p != NULL)
{
ancestors.insert(p);
p = parent.find(p) != parent.end() ? parent[p] : nullptr;
}
while (ancestors.find(q) == ancestors.end())
q = parent.find(q)!=parent.end() ? parent[q] : nullptr;
return q;
}
};
```
recursive solution
==Tree 先以single node 來思考==
recursive 會從最底開始bottom-up
three situations
1. both p and q are find in the subtrees -> root is the lca
2. p q is in the same subtree -> the higher one is lca
3. no p q in both subtree -> return null
pseudo code
```cpp
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || p == root || q == root) return root;
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p , q);
if (left && right) return root;
return left ? left : right;
}
};
```
## Unique Binary Search Trees
solve it by divide and conquer
Adding DP to reduce time complexity
很明顯地，DP[0] = 1(空樹)且DP[1] = 1(只有一個node)，而當DP[2]的狀況，我們就可以分成以2與1為根的狀況，自然D
P[2]=2。這樣或許還看不出每個sub-problems之間的關係，但我們可以用DP[3]來找到其關聯性。
在DP[3]的case，依照DP[2]的經驗，因為我們有1,2和3三個node，我們分別用它們三個來當root。首先，我們先用3來當root，而依照剛剛的特性，我們使用3當root，其左子樹所有node必定小於3，其實也就是使用1與2兩個node來形成BST，那不就是DP[2]了呢？而右子樹因為沒有大於3的node，就是DP[0] (空樹)了，所以在3為root的狀況排列組合就是DP[2] * DP[0] = 2。
我們再來看另一個1為root的狀況，同理，其左子樹為空樹，而其右子樹就可以等化成用2,3來形成BST，但因為右子樹的BST並沒有額外的限制，因此用1,2或者2,3基本上都是一樣的意思因此在1為root的排列組合就是DP[0]*DP[2] = 2。而一樣的道理，在2為root的情況就是DP[1] * DP[1] = 1了，三者加總的結果就是題目範例的結果5，下圖整理了DP[3]排列方式：
Bottom-up DP
```cpp
class Solution {
public:
int numTrees(int n) {
//Time complexity: O(n^2) space complexity: O(n)
// DP[i] = 擁有i個node(1…i)的BST總共有幾種排法
if(n == 0) return 1;
vector<int> dp(n+1, 0);
dp[0] = 1;
dp[1] = 1;
for(int i = 2;i <= n;++i) { // 有幾棵樹，從2開始
for(int j = 0;j < i;++j) { // j is the root
dp[i] += dp[j] * dp[i-j-1];
}
}
return dp.back();
}
};
```
<br><br>
## Inorder Successor in BST
```Initial```
```Imporvement```
將兩種情況的第二優先順序整合，成為尋找第一個>p的parent
```cpp
// Iterative
class Solution {
public:
/*
* @param root: The root of the BST.
* @param p: You need find the successor node of p.
* @return: Successor of p.
*/
TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
TreeNode * fa = NULL; // fa is the first parent that is bigger than p, only change when go left
while (root && root != p) {
if (root->val < p->val)
root = root->right;
else {
fa = root;
root = root->left;
}
}
if (root == NULL)
return NULL;
if (root->right == NULL)
return fa;
root = root->right;
while (root->left)
root = root->left;
return root;
}
};
```
==注意最後一句!!!!!==
```cpp
// Recursive
// Hard to understand
// when root>p, then there are two possibles for the answer, root itself and recursive output of left subtree
// when root<p, the answer can only be in right subtree
// Example, 12 is p in the picture above, and node 10 and 14 is not exist in this case
//
// 20 will call left recursive which will end up with NULL by right recursive, thus, 20 is the answer
class Solution {
public:
/*
* @param root: The root of the BST.
* @param p: You need find the successor node of p.
* @return: Successor of p.
*/
TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
if (root == NULL)
return NULL;
if (root->val <= p->val)
return inorderSuccessor(root->right, p);
TreeNode * left = inorderSuccessor(root->left, p);
return left ? left : root;
}
};
```
## Unique Binary Search Trees II
### ==Learn how to use auto==
1. auto : x (vector) -> can iterate through x for(auto : x)
2. auto x = 1 -> equal to int x = 1
[auto](https://blog.gtwang.org/programming/cpp-auto-variable-tutorial/)
solve it by divide and conquer
```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
if (n == 0) return {};
return helper(1, n);
}
vector<TreeNode*> helper(int start, int end) {
if (start > end) return {nullptr};
vector<TreeNode*> res;
for (int i = start; i <= end; ++i) {
auto left = helper(start, i - 1), right = helper(i + 1, end);
for (auto a : left) {
for (auto b : right) {
TreeNode *node = new TreeNode(i);
node->left = a;
node->right = b;
res.push_back(node);
}
}
}
return res;
}
};
```
## Serilaize and Deserialize Binary tree ==Hard==
```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res;
queue <TreeNode*> q;
if(!root) return res;
q.push(root);
while(!q.empty()){
TreeNode* cur = q.front();
q.pop();
if(cur){
res += to_string(cur->val)+" ";
q.push(cur->left);
q.push(cur->right);
}
else{
res=res+"# ";
}
}
return res;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data.empty()) {
return NULL;
}
istringstream iss (data);
string x;
queue<TreeNode*> q;
iss >> x;
TreeNode* root = new TreeNode(stoi(x));
q.push(root);
//it is the same as bfs
while (iss >> x) {
TreeNode *cur = q.front();
q.pop();
//the x is already generated in while condition
cur->left = x == "#" ? NULL : new TreeNode(stoi(x));
iss >> x;
cur->right = x == "#" ? NULL : new TreeNode(stoi(x));
//same here, we no longer need to put null ptr into the queue, because it do not need to find its child
if (cur->left) {
q.push(cur->left);
}
if (cur->right) {
q.push(cur->right);
}
}
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
```
Sign in with Wallet
Connect another wallet