首页 > 编程语言 >代码随想录算法训练营第19天|235. 二叉搜索树的最近公共祖先 ,701.二叉搜索树中的插入操作,450.删除二叉搜索树中的节点

代码随想录算法训练营第19天|235. 二叉搜索树的最近公共祖先 ,701.二叉搜索树中的插入操作,450.删除二叉搜索树中的节点

时间:2024-11-10 12:09:04浏览次数:5  
标签:TreeNode val root 二叉 搜索 NULL 树中 left

235. 二叉搜索树的最近公共祖先

文章链接:https://programmercarl.com/0235.二叉搜索树的最近公共祖先.html
题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/

思路:利用二叉搜索树的特性,当第一次遇到在[p,q]区间或[q,p]区间的元素的节点,则该节点一定是p和q的最近公共祖先
此题为只搜索一条边而不是搜索一整个树的题,可以和前面的题进行区分。所以不用考虑前中后序,只需要从root开始进行判断,从而确定是向左遍历还是向右遍历。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root->val>p->val&&root->val>q->val) return lowestCommonAncestor(root->left,p,q);
        if(root->val<p->val&&root->val<q->val) return lowestCommonAncestor(root->right,p,q);
        return root;
    }
};

701.二叉搜索树中的插入操作

文章链接:https://programmercarl.com/0701.二叉搜索树中的插入操作.html
题目链接:https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root==NULL){
            TreeNode* node=new TreeNode(val);
            root=node;
        }
        if(root->val<val) root->right=insertIntoBST(root->right,val);
        if(root->val>val) root->left=insertIntoBST(root->left,val);
        return root;
    }
};

450.删除二叉搜索树中的节点

文章链接:https://programmercarl.com/0450.删除二叉搜索树中的节点.html
题目链接:https://leetcode.cn/problems/delete-node-in-a-bst/description/

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        //终止条件
        if(root==NULL) return NULL;  //root为空的情况
        if(root->val==key){ //root不为空的情况
            if(root->left==NULL&&root->right==NULL){  //root为叶子节点的情况
                delete root;
                return NULL;
            }
            if(root->left!=NULL&&root->right==NULL){  //root左子树不空,右子树空
                TreeNode* node=root->left;
                delete root;
                return node;
            }
            else if(root->left==NULL&&root->right!=NULL){  //root左子树空,右子树不空
                TreeNode* node=root->right;
                delete root;
                return node;
            }
            else{  //root左右子树都不为空
                TreeNode* cur=root->right;
                while(cur->left!=NULL) cur=cur->left;
                cur->left=root->left;
                TreeNode* node=root->right;
                delete root;
                return node;
            }
        }
        //递归
        if(root->val>key) root->left=deleteNode(root->left,key);
        else if(root->val<key) root->right=deleteNode(root->right,key);
        return root;
    }
};

标签:TreeNode,val,root,二叉,搜索,NULL,树中,left
From: https://www.cnblogs.com/VickyWu/p/18537835

相关文章

  • 根据二叉树创建字符串
    题目:606.根据二叉树创建字符串-力扣(LeetCode)给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造出的字符串。空节点使用一对空括号对 "()" 表示,转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空......
  • 代码随想录算法训练营第18天| 530.二叉搜索树的最小绝对差, 501.二叉搜索树中的众数 , 2
    530.二叉搜索树的最小绝对差文章链接:https://programmercarl.com/0530.二叉搜索树的最小绝对差.html视频链接:https://www.bilibili.com/video/BV1DD4y11779/?vd_source=6cb513d59bf1f73f86d4225e9803d47b题目链接:https://leetcode.cn/problems/minimum-absolute-difference-in......
  • 判断该给定的二叉树是否为二叉搜索树
    习题4.3是否二叉搜索树/*typedefstructTNode*Position;typedefPositionBinTree;structTNode{ ElementTypeData; BinTreeLeft; BinTreeRight;};*/BinTreeB=NULL;//全局指针,用来记录中序的上一个结点boolIsBST(BinTreeT){ //如果结点为空直接返回tru......
  • 将给定的表达式树(二叉链表存储)转换为等价的中缀表达式(递归)
    3765.表达式树可以拿这题验证自己的代码对不对ps:这里不是这题的答案,参照代码思路写即可voidBtreeToe(Btree*root){ BtreeToExp(root,1);//根的高度为1 }voidBtreeToExp(Btree*root,intdep){ if(root==NULL)return;//如果是空结点返回 elseif(!root->lef......
  • 力扣(LeetCode)106. 从中序与后序遍历序列构造二叉树
    一、目标  给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。二、代码分析总体代码:/***Definitionforabinarytreenode.*publicclassTreeNode{*int......
  • 104.力扣(leetcode)二叉树的最大深度(JAVA)
    一、目标给定一个二叉树 root ,返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。二、代码分析总代码:/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeN......
  • 257. 力扣(LeetCode)二叉树的所有路径(JAVA)
    一、目标给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。二、代码解读总代码:/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*......
  • 程序员 SEO 系列:如何找到更多搜索关键词?
    本文分享有效的关键词挖掘策略,帮助你识别低竞争、高流量的蓝海关键词,提升网站排名并带来持续流量增长。了解如何通过竞品分析、长尾词挖掘等方法,发掘适合你网站的关键词,快速提升SEO效果。一、关键词研究(挖词)的目的?SEO挖词的目的是通过深入Research和识别有流量潜力的关键词......
  • 代码随想录算法训练营第十七天| 654.最大二叉树 , 617.合并二叉树 , 700.二叉搜索树中的
    654.最大二叉树文章链接:https://programmercarl.com/0654.最大二叉树.html题目链接:https://leetcode.cn/problems/maximum-binary-tree/description/classSolution{public:TreeNode*traversal(vector<int>&nums,intleft,intright){if(left>=right)ret......
  • 二叉搜索树
    一.二叉搜索树介绍    二叉搜索树又叫做二叉排序树,它拥有一些特殊的性质。    1.若它的左子树不为空,那么左子树上面的节点全部小于根节点。    2.若它的右子树不为空,那么右子树上面的节点全部大于根节点。    3.它的左右子树也全部都是二......