二叉搜索树算法题学习

//leetcode700 二叉搜索树中的搜索
TreeNode* searchBST(TreeNode* root, int val) {
    if(root == nullptr || root->val == val)  return root;
    if(root->val > val) return searchBST(root->left,val);
    if(root->val < val) return searchBST(root->right,val);
    return nullptr;
}

//leetcode 669 修剪二叉搜索树
TreeNode* trimBST(TreeNode* root, int low, int high) {
    if(root == nullptr) return root;
    if(root->val < low) return trimBST(root->right,low,high);
    if(root->val > high) return trimBST(root->left,low,high);
    root -> left = trimBST(root -> left, low, high);
    root -> right = trimBST(root -> right, low, high);
    return root;
}

//leetcode 538、1038 把二叉搜索树转换成累加树
int sum = 0;
TreeNode* convertBST(TreeNode* root) {
    if(root != nullptr)
    {
        convertBST(root->right);
        sum += root->val;
        root->val = sum;
        convertBST(root->left);
    }
    return root;
}

//leetcode 235 二叉搜索树的最近公共祖先
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int rootval = root->val;
        int pval = p->val;
        int qval = q->val;
        if(pval > rootval && qval > rootval)
        {
            return lowestCommonAncestor(root->right,p,q);
        }else if(pval < rootval && qval < rootval)
        {
            return lowestCommonAncestor(root->left,p,q);
        }else
        {
            return root;
        }
} 

//leetcode1373. 二叉搜索子树的最大键值和
class Solution
{
    public:
        int maxSumBST(TreeNode* root)
        {
            int ans = 0;
            dfs(root,&ans);
            return ans; 
        }   

    private:
        tuple<int,int,int,bool> dfs(TreeNode* root,int *ans)
        {
            if(!root) return {INT_MAX,INT_MIN,0,true};
            auto [ll,lh,ls,lv] = dfs(root->left,ans);
            auto [rl,rh,rs,rv] = dfs(root->right,ans);
            bool valid = lv && rv && root->val >lh && root->val < rl;
            int sum = valid ? ls + rs + root->val : -1;
            *ans = max(*ans,sum);
            return {min(ll,root->val),max(rh,root->val),sum,valid};
        }
};

//面试04 03 最下高度树
//给定一个有序整数数组,元素各不相同且按升序排列,编写一个算法,创建一棵高度最小的二叉搜索树.
TreeNode* dfs(const vector<int> &nums,int L,int R)
{
    if(L > R)
        return 0;
    int mid = (L + R)>>1;
    auto ptr = new TreeNode(nums[mid]);
    ptr->left = dfs(nums,L,mid-1);
    ptr->right = dfs(nums,mid+1,R);
    return ptr;
}

TreeNode* sortedArrayToBST(vector<int>& nums) {
    return dfs(nums,0,nums.size()-1);
} 

//leetcode270 最接近的二叉搜索树值
//请在该二叉搜索树中找到最接近目标值target的数值。
class Solution270
{
    public:
        int closestValue(TreeNode *root,double target)
        {
            int val,cloest = root->val;
            while(root != nullptr)
            {
                val = root->val;
                cloest = abs(val - target) < abs(cloest - target) ? val : cloest;
                root = target < root->val ? root->left : root->right;
            }   
            return cloest;
        }   
};

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。