/**
 * 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) {}
 * };
 */

/**
 * 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:
    TreeNode* searchBST(TreeNode* root, int val) {
        //if root is null return null
        if(!root) return root;
        //create node to return 
        TreeNode *node=new TreeNode(); 
        // if root->val != val,search in left and right
        //otherwise this would be required node and we would return it
        if(val<root->val){
            //search in left 
            node=searchBST(root->left,val);
        } else if(val>root->val){
            //search in right
            node=searchBST(root->right,val);
        } else {
            //required node
            node=root;
        }
        return node;
    }
};

class Solution {
public:
    int fib(int n) {
        int sum=0;

        if (n==2)
        {
            return 1;
        }
        if (n==1)
        {
            return 1;
                
        }
        if (n==0)
        {
            return 0;
        }
        else
        {
            sum=sum+fib(n-1)+fib(n-2);
            n=n-1;
        }
        return sum;
    }
};

def divide_and_conquer(S):
    #(1)Divide the problem into a set of subproblem
    [S1,S2,...Sn]=divide(S)
    #2 solve the subproblem
    #obtain the result of subproblem
    ret=[divide_and_conquer(Si) for Si in [S1..Sn]]
    [R1,R2..Rn]=rets
    #3combine
    return combine([R1,R2,..Rn])