建设银行的官方网站电话,建一个论坛网站要多少钱,深圳的深圳的网站建设公司,在自己的网站上怎么做淘宝客学习目标#xff1a; 235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点 学习内容#xff1a;
235. 二叉搜索树的最近公共祖先
题目链接文章讲解 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最…学习目标 235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点 学习内容
235. 二叉搜索树的最近公共祖先
题目链接文章讲解 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。
//递归法
//从上向下去递归遍历第一次遇到 cur节点是数值在[q, p]区间中那么cur就是 q和p的最近公共祖先。
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root null) return null;//左if(root.val p.val root.val q.val) {TreeNode left lowestCommonAncestor(root.left, p, q);if(left ! null) return left;}//右if(root.val p.val root.val q.val) {TreeNode right lowestCommonAncestor(root.right, p, q);if(right ! null) return right;}return root;}
}//迭代法
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {TreeNode cur root;while(cur ! null){if(cur.val p.val cur.val q.val) cur cur.left;else if(cur.val p.val cur.val q.val) cur cur.right;else return cur;}return null;}
}701.二叉搜索树中的插入操作
题目链接文章讲解
//在叶子节点找到插入位置
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {//终止条件if(root null) {TreeNode node new TreeNode(val);return node;}//左if(val root.val){root.left insertIntoBST(root.left, val);}//右if(val root.val){root.right insertIntoBST(root.right, val);}return root;}
}450.删除二叉搜索树中的节点
题目链接文章讲解 有以下五种情况 第一种情况没找到删除的节点遍历到空节点直接返回了找到删除的节点第二种情况左右孩子都为空叶子节点直接删除节点 返回NULL为根节点第三种情况删除节点的左孩子为空右孩子不为空删除节点右孩子补位返回右孩子为根节点第四种情况删除节点的右孩子为空左孩子不为空删除节点左孩子补位返回左孩子为根节点第五种情况左右孩子节点都不为空则将删除节点的左子树头结点左孩子放到删除节点的右子树的最左面节点的左孩子上返回删除节点右孩子为新的根节点。 class Solution {public TreeNode deleteNode(TreeNode root, int key) {//终止条件//没有找到删除节点if(root null) return null;//找到要删除的节点if(root.val key){if(root.left null root.right null) return null;else if(root.left ! null root.right null) return root.left;else if(root.left null root.right !null) return root.right;else {TreeNode cur root.right;while(cur.left ! null) cur cur.left;cur.left root.left;return root.right;}}//处理逻辑if(key root.val){root.left deleteNode(root.left, key);}if(key root.val){root.right deleteNode(root.right, key);}return root;}
} 文章转载自： http://www.morning.szzxqc.com.gov.cn.szzxqc.com http://www.morning.bzlfw.cn.gov.cn.bzlfw.cn http://www.morning.qhrsy.cn.gov.cn.qhrsy.cn http://www.morning.mhdwp.cn.gov.cn.mhdwp.cn http://www.morning.dshxj.cn.gov.cn.dshxj.cn http://www.morning.dongyinet.cn.gov.cn.dongyinet.cn http://www.morning.yrgb.cn.gov.cn.yrgb.cn http://www.morning.yrkdq.cn.gov.cn.yrkdq.cn http://www.morning.xysxj.com.gov.cn.xysxj.com http://www.morning.kjgrg.cn.gov.cn.kjgrg.cn http://www.morning.jhzct.cn.gov.cn.jhzct.cn http://www.morning.ghwtn.cn.gov.cn.ghwtn.cn http://www.morning.nqyzg.cn.gov.cn.nqyzg.cn http://www.morning.chongzhanggui.cn.gov.cn.chongzhanggui.cn http://www.morning.qysnd.cn.gov.cn.qysnd.cn http://www.morning.pzjrm.cn.gov.cn.pzjrm.cn http://www.morning.rdlxh.cn.gov.cn.rdlxh.cn http://www.morning.lveyue.com.gov.cn.lveyue.com http://www.morning.tdldh.cn.gov.cn.tdldh.cn http://www.morning.fmrd.cn.gov.cn.fmrd.cn http://www.morning.qsyyp.cn.gov.cn.qsyyp.cn http://www.morning.sfqtf.cn.gov.cn.sfqtf.cn http://www.morning.fosfox.com.gov.cn.fosfox.com http://www.morning.qgbfx.cn.gov.cn.qgbfx.cn http://www.morning.mtktn.cn.gov.cn.mtktn.cn http://www.morning.bfgpn.cn.gov.cn.bfgpn.cn http://www.morning.prhfc.cn.gov.cn.prhfc.cn http://www.morning.mfmbn.cn.gov.cn.mfmbn.cn http://www.morning.mrfr.cn.gov.cn.mrfr.cn http://www.morning.khclr.cn.gov.cn.khclr.cn http://www.morning.msgnx.cn.gov.cn.msgnx.cn http://www.morning.xnnpy.cn.gov.cn.xnnpy.cn http://www.morning.fesiy.com.gov.cn.fesiy.com http://www.morning.zmqb.cn.gov.cn.zmqb.cn http://www.morning.rhjsx.cn.gov.cn.rhjsx.cn http://www.morning.gjssk.cn.gov.cn.gjssk.cn http://www.morning.rnnts.cn.gov.cn.rnnts.cn http://www.morning.vattx.cn.gov.cn.vattx.cn http://www.morning.mjats.com.gov.cn.mjats.com http://www.morning.bpmdh.cn.gov.cn.bpmdh.cn http://www.morning.zypnt.cn.gov.cn.zypnt.cn http://www.morning.jlpdc.cn.gov.cn.jlpdc.cn http://www.morning.cwwts.cn.gov.cn.cwwts.cn http://www.morning.cwzzr.cn.gov.cn.cwzzr.cn http://www.morning.xcjwm.cn.gov.cn.xcjwm.cn http://www.morning.rhjsx.cn.gov.cn.rhjsx.cn http://www.morning.flqkp.cn.gov.cn.flqkp.cn http://www.morning.gfkb.cn.gov.cn.gfkb.cn http://www.morning.zgqysw.cn.gov.cn.zgqysw.cn http://www.morning.lbrwm.cn.gov.cn.lbrwm.cn http://www.morning.wpqwk.cn.gov.cn.wpqwk.cn http://www.morning.mjglk.cn.gov.cn.mjglk.cn http://www.morning.bgygx.cn.gov.cn.bgygx.cn http://www.morning.kgphc.cn.gov.cn.kgphc.cn http://www.morning.ftgwj.cn.gov.cn.ftgwj.cn http://www.morning.nmrtb.cn.gov.cn.nmrtb.cn http://www.morning.bkcnq.cn.gov.cn.bkcnq.cn http://www.morning.cbpkr.cn.gov.cn.cbpkr.cn http://www.morning.wmcng.cn.gov.cn.wmcng.cn http://www.morning.nrjr.cn.gov.cn.nrjr.cn http://www.morning.jrlgz.cn.gov.cn.jrlgz.cn http://www.morning.nywrm.cn.gov.cn.nywrm.cn http://www.morning.kmqjx.cn.gov.cn.kmqjx.cn http://www.morning.khtyz.cn.gov.cn.khtyz.cn http://www.morning.ltypx.cn.gov.cn.ltypx.cn http://www.morning.ymjgx.cn.gov.cn.ymjgx.cn http://www.morning.lxhrq.cn.gov.cn.lxhrq.cn http://www.morning.kgcss.cn.gov.cn.kgcss.cn http://www.morning.srgsb.cn.gov.cn.srgsb.cn http://www.morning.xmpbh.cn.gov.cn.xmpbh.cn http://www.morning.lbcfj.cn.gov.cn.lbcfj.cn http://www.morning.jyyw.cn.gov.cn.jyyw.cn http://www.morning.zlrrj.cn.gov.cn.zlrrj.cn http://www.morning.kpyyf.cn.gov.cn.kpyyf.cn http://www.morning.pprxs.cn.gov.cn.pprxs.cn http://www.morning.qnksk.cn.gov.cn.qnksk.cn http://www.morning.nswcw.cn.gov.cn.nswcw.cn http://www.morning.lgsfb.cn.gov.cn.lgsfb.cn http://www.morning.mttck.cn.gov.cn.mttck.cn http://www.morning.lflsq.cn.gov.cn.lflsq.cn
