---
# System prepended metadata

title: Tree
tags: [Study_aboard]

---

# 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)

![](https://i.imgur.com/OHb7n9T.png)


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
![](https://i.imgur.com/2F7Pk38.png)
![](https://i.imgur.com/f0ki0Wy.png)
![](https://i.imgur.com/CK6C4H6.png)
```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
![](https://i.imgur.com/DXhMzP7.png)
![](https://i.imgur.com/VNAOFYx.png)

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

![](https://i.imgur.com/ENYHmqe.png)

```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
![](https://i.imgur.com/dxIhZNl.png)
![](https://i.imgur.com/hUCglmR.png)

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
![](https://i.imgur.com/k5llRFj.png)
![](https://i.imgur.com/owPwqy0.png)

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
![](https://i.imgur.com/Y8MIdKr.png)
![](https://i.imgur.com/bsIOSNl.png)
![](https://i.imgur.com/BqZTbpn.png)
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 
![](https://i.imgur.com/0PfBQld.png)
![](https://i.imgur.com/JkKJueK.png)


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
![](https://i.imgur.com/2ukbzxc.png)
![](https://i.imgur.com/Qxm7EuV.png)

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
![](https://i.imgur.com/XjQEGBQ.png)
![](https://i.imgur.com/XuEJ1Pv.png)
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

![](https://i.imgur.com/nO3ItX0.png)

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

![](https://i.imgur.com/tl9HRiP.png)


```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
![](https://i.imgur.com/1fRCKog.png)
![](https://i.imgur.com/sd7qS78.png)
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
![](https://i.imgur.com/EQJ8xih.png)
![](https://i.imgur.com/JwAdwAB.png)

Sol: 
通過樹上節點的相對位置，我們可以對樹節點進行編號，左節點的列編號值是當前節點的列編號減一，右節點的列編號是當前節點的列編號加一。通過一次深度優先或寬度優先遍曆，就可以得到這些節點的列編號。

如果用DFS遍歷將列編號按遍歷順序加入答案結果，可能會導致，同一列的陣列中節點的編號沒有按照節點深度排序。所以採用BFS更優秀，可以按深度將同一列節點按順序加入陣列。(參考下圖)
![](https://i.imgur.com/2qcZHyk.png)



```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
![](https://i.imgur.com/0vHdc13.png)
```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 
![](https://i.imgur.com/BRc7Gfy.png)

```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 

![](https://i.imgur.com/syd9LPT.png)

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
![](https://i.imgur.com/v7uZfyZ.png)
```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

![](https://i.imgur.com/dZlTjhy.png)
![](https://i.imgur.com/JdXPacg.png)

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

![](https://i.imgur.com/V8h77dc.png)


pseudo code

![](https://i.imgur.com/tD4DtJ4.png)


```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

![](https://i.imgur.com/ItSgnGs.png)

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]排列方式：

![](https://i.imgur.com/6Fnjh6g.png)

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
![](https://i.imgur.com/y50SYHy.png)
![](https://i.imgur.com/d3N3zwz.png)
![](https://i.imgur.com/Cz8cGs7.png)
![](https://i.imgur.com/0SFkt2G.png)
```Initial```
![](https://i.imgur.com/3bP2exP.png)

```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;
    }
};
```

![](https://i.imgur.com/JdNu0aX.png)

==注意最後一句!!!!!==

```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/)

![](https://i.imgur.com/InMZQLH.png)

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==
![](https://i.imgur.com/JkXoAfj.png)
![](https://i.imgur.com/w5SOEUK.png)

```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));
```
