429- binary tree (108. convert the ordered array into a binary search tree, 538. convert the binary search tree into an accumulation tree, 106. construct a binary tree from the middle order and post o

108. Convert an ordered array to a binary search tree

class Solution {
    
public:
    TreeNode* traversal(vector<int>& nums, int left, int right)
    {
    
        if (left > right)    return nullptr;
        int mid = left + ((right - left) / 2);
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = traversal(nums, left, mid - 1);
        root->right = traversal(nums, mid + 1, right);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
    
        TreeNode* root = traversal(nums, 0, nums.size() - 1);
        return root;
    }
};

538. Convert binary search tree to accumulation tree

class Solution {
    
private:
    int pre;

    void traversal(TreeNode* cur)
    {
    
        if (cur == nullptr)  return;
        traversal(cur->right);
        cur->val += pre;
        pre = cur->val;
        traversal(cur->right);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
    
        pre = 0;
        traversal(root);
        return root;
    }
};

106. Construct binary tree from middle order and post order traversal sequence

class Solution {
    

public:
    TreeNode* traversal(vector<int>& inorder, vector<int>& postorder) {
    
        if (postorder.size() == 0)    return nullptr;


        // After traversing the last element of the array , As the current intermediate node 
        int rootValue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootValue);

        // Leaf node 
        if (postorder.size() == 1)   return root;

        //  Find the cutting point of the middle order traversal 
        int del;
        for (del = 0; del < inorder.size(); del++)
        {
    
            if (inorder[del] == rootValue)   break;
        }

        //  Cut the ordered array 
       //  Left closed right open interval ：[0, delimiterIndex)
        vector<int> leftInorder(inorder.begin(), inorder.begin() + del);
        vector<int> rightInorder(inorder.begin() + del + 1, inorder.end());

        // postorder  Discard end element 
        postorder.resize(postorder.size() - 1);

        // Cut subsequent arrays 
        vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);

        return root;
    }

public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
    {
    
        if (inorder.size() == 0 || postorder.size() == 0)    return nullptr;
        return traversal(inorder, postorder);
    }
};

235. The nearest common ancestor of a binary search tree

class Solution {
    
public:
    TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
    
        if (cur == nullptr)  return cur;

        if (cur->val > p->val && cur->val > q->val)
        {
    
            TreeNode* left = traversal(cur->left, p, q);
            if (left != nullptr)
            {
    
                return left;
            }
        }

        if (cur->val < p->val && cur->val < q->val)
        {
    
            TreeNode* right = traversal(cur->right, p, q);
            if (right != nullptr)
            {
    
                return right;
            }
        }
        return cur;
    }

public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
        return traversal(root, p, q);
    }
};