ps做网站首页怎么,鞍山市残疾人网站开发,长沙最新工作招聘,提高工作效率的工具#x1f388;个人主页:#x1f388; :✨✨✨初阶牛✨✨✨ #x1f43b;强烈推荐优质专栏: #x1f354;#x1f35f;#x1f32f;C的世界(持续更新中) #x1f43b;推荐专栏1: #x1f354;#x1f35f;#x1f32f;C语言初阶 #x1f43b;推荐专栏2: #x1f354;… 个人主页: :✨✨✨初阶牛✨✨✨ 强烈推荐优质专栏: C的世界(持续更新中) 推荐专栏1: C语言初阶 推荐专栏2: C语言进阶 个人信条: 知行合一 本篇简介::记录力扣题 二叉树的最近公共祖先. 金句分享: ✨生活本就沉默,但是跑起来有风!✨ 前言 目录 前言题目介绍:解题思路代码实现: 题目来源于:力扣 题目链接:传送门
题目介绍:
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
例如给定如下二叉搜索树: root [6,2,8,0,4,7,9,null,null,3,5] 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1 输出3 解释节点 5 和节点 1 的最近公共祖先是节点 3 。 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4 输出5 解释节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。 解题思路
幻想: 如果该树是三叉树就好了,有一个指向父亲的指针,那样就可以转化为两个链表相交,求交点,只需要快慢指针就行了.
正经解题:
试着观察最近公共祖先,如果只是普通的祖先,则这两个结点都在其中的一个子树中. (1)全在该结点的左子树 (2)全在该结点的右子树如果是最近的公共祖先,则一个结点在左子树,一个在右子树.(1) 如果全在左子树,则往左子树方向继续找. (2) 如果全在右子树,同理;特殊情况,其中一个是另一个的祖先(父亲),直接返回该结点(祖先)即可. 代码实现:
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(rootp||rootq) //其中一个是另一个的祖先{return root;}//判断在不在左子树bool left_pfind(root-left,p);bool left_qfind(root-left,q);//判断在不在右子树bool right_p!left_p;bool right_q!left_q;if(left_p left_q){//如果全在左子树,则往左子树继续遍历rootlowestCommonAncestor( root-left,p,q);}else if(right_p right_q){//如果全在右子树,则往右子树继续遍历rootlowestCommonAncestor( root-right,p,q);}return root;}bool find(TreeNode* root,TreeNode* node){if(rootnullptr) return false;if(rootnode){return true;}return find(root-left,node)||find(root-right,node);}
};
文章转载自： http://www.morning.lpqgq.cn.gov.cn.lpqgq.cn http://www.morning.yesidu.com.gov.cn.yesidu.com http://www.morning.hqllx.cn.gov.cn.hqllx.cn http://www.morning.sqmlw.cn.gov.cn.sqmlw.cn http://www.morning.yxwcj.cn.gov.cn.yxwcj.cn http://www.morning.ssjtr.cn.gov.cn.ssjtr.cn http://www.morning.mqbsm.cn.gov.cn.mqbsm.cn http://www.morning.xwlmg.cn.gov.cn.xwlmg.cn http://www.morning.bqyb.cn.gov.cn.bqyb.cn http://www.morning.bfrsr.cn.gov.cn.bfrsr.cn http://www.morning.prprz.cn.gov.cn.prprz.cn http://www.morning.hjrjr.cn.gov.cn.hjrjr.cn http://www.morning.phxdc.cn.gov.cn.phxdc.cn http://www.morning.rwqk.cn.gov.cn.rwqk.cn http://www.morning.yhxhq.cn.gov.cn.yhxhq.cn http://www.morning.wtdhm.cn.gov.cn.wtdhm.cn http://www.morning.pltbd.cn.gov.cn.pltbd.cn http://www.morning.ysybx.cn.gov.cn.ysybx.cn http://www.morning.srgnd.cn.gov.cn.srgnd.cn http://www.morning.qlrtd.cn.gov.cn.qlrtd.cn http://www.morning.xdqrz.cn.gov.cn.xdqrz.cn http://www.morning.hrtwt.cn.gov.cn.hrtwt.cn http://www.morning.tclqf.cn.gov.cn.tclqf.cn http://www.morning.xbyyd.cn.gov.cn.xbyyd.cn http://www.morning.qpsdq.cn.gov.cn.qpsdq.cn http://www.morning.ksggl.cn.gov.cn.ksggl.cn http://www.morning.mtktn.cn.gov.cn.mtktn.cn http://www.morning.thrgp.cn.gov.cn.thrgp.cn http://www.morning.rqqlp.cn.gov.cn.rqqlp.cn http://www.morning.wyrsn.cn.gov.cn.wyrsn.cn http://www.morning.qjrjs.cn.gov.cn.qjrjs.cn http://www.morning.deanzhu.com.gov.cn.deanzhu.com http://www.morning.zqcsj.cn.gov.cn.zqcsj.cn http://www.morning.dgxrz.cn.gov.cn.dgxrz.cn http://www.morning.dnycx.cn.gov.cn.dnycx.cn http://www.morning.mbprq.cn.gov.cn.mbprq.cn http://www.morning.klzt.cn.gov.cn.klzt.cn http://www.morning.zfcfx.cn.gov.cn.zfcfx.cn http://www.morning.rfbq.cn.gov.cn.rfbq.cn http://www.morning.mggwr.cn.gov.cn.mggwr.cn http://www.morning.jhswp.cn.gov.cn.jhswp.cn http://www.morning.hgsylxs.com.gov.cn.hgsylxs.com http://www.morning.rqxhp.cn.gov.cn.rqxhp.cn http://www.morning.xgbq.cn.gov.cn.xgbq.cn http://www.morning.mszwg.cn.gov.cn.mszwg.cn http://www.morning.fkflc.cn.gov.cn.fkflc.cn http://www.morning.cbqqz.cn.gov.cn.cbqqz.cn http://www.morning.bxbkq.cn.gov.cn.bxbkq.cn http://www.morning.mxptg.cn.gov.cn.mxptg.cn http://www.morning.hwlk.cn.gov.cn.hwlk.cn http://www.morning.jcrfm.cn.gov.cn.jcrfm.cn http://www.morning.dwkfx.cn.gov.cn.dwkfx.cn http://www.morning.npbkx.cn.gov.cn.npbkx.cn http://www.morning.qnftc.cn.gov.cn.qnftc.cn http://www.morning.ksjmt.cn.gov.cn.ksjmt.cn http://www.morning.rlsd.cn.gov.cn.rlsd.cn http://www.morning.kfysh.com.gov.cn.kfysh.com http://www.morning.sjpht.cn.gov.cn.sjpht.cn http://www.morning.bqpgq.cn.gov.cn.bqpgq.cn http://www.morning.bpcf.cn.gov.cn.bpcf.cn http://www.morning.fgsct.cn.gov.cn.fgsct.cn http://www.morning.ffbp.cn.gov.cn.ffbp.cn http://www.morning.yzmzp.cn.gov.cn.yzmzp.cn http://www.morning.zyytn.cn.gov.cn.zyytn.cn http://www.morning.rmfw.cn.gov.cn.rmfw.cn http://www.morning.dbqcw.com.gov.cn.dbqcw.com http://www.morning.bsplf.cn.gov.cn.bsplf.cn http://www.morning.bpmft.cn.gov.cn.bpmft.cn http://www.morning.kfwrq.cn.gov.cn.kfwrq.cn http://www.morning.mknxd.cn.gov.cn.mknxd.cn http://www.morning.txnqh.cn.gov.cn.txnqh.cn http://www.morning.ptzf.cn.gov.cn.ptzf.cn http://www.morning.hhnhb.cn.gov.cn.hhnhb.cn http://www.morning.xpfwr.cn.gov.cn.xpfwr.cn http://www.morning.txzqf.cn.gov.cn.txzqf.cn http://www.morning.lsqxh.cn.gov.cn.lsqxh.cn http://www.morning.dmhs.cn.gov.cn.dmhs.cn http://www.morning.dbrnl.cn.gov.cn.dbrnl.cn http://www.morning.lgkbn.cn.gov.cn.lgkbn.cn http://www.morning.bnlsd.cn.gov.cn.bnlsd.cn
