文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

二叉树的最近公共祖先

二叉树的最近公共祖先 力扣链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先...思路 遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了。 那么二叉树如何可以自底向上查找呢？ 回溯啊，二叉树回溯的过程就是从低到上。...直观上来看，找到最近公共祖先，直接一路返回就可以了。 如图： 236.二叉树的最近公共祖先 就像图中一样直接返回7，多美滋滋。...如图： 236.二叉树的最近公共祖先1 图中节点10的左子树返回null，右子树返回目标值7，那么此时节点10的处理逻辑就是把右子树的返回值（最近公共祖先7）返回上去！...，完整流程图如下： 236.二叉树的最近公共祖先2 从图中，大家可以看到，我们是如何回溯遍历整颗二叉树，将结果返回给头结点的！

2.3K20
您找到你想要的搜索结果了吗？
是的
没有找到

二叉树的最近公共祖先

个人主页: :✨✨✨初阶牛✨✨✨ 强烈推荐优质专栏: C++的世界(持续更新中) 推荐专栏1: C语言初阶 推荐专栏2: C语言进阶 个人信条: 知行合一 本篇简介:>:记录力扣题 二叉树的最近公共祖先...✨ 题目介绍: 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。...百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”...正经解题: 试着观察最近公共祖先,如果只是普通的祖先,则这两个结点都在其中的一个子树中....(1)全在该结点的左子树 (2)全在该结点的右子树 如果是最近的公共祖先,则一个结点在左子树,一个在右子树. (1) 如果全在左子树,则往左子树方向继续找.

20110

二叉树-最近的公共祖先

已知二叉树，求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u，满足在树上最低(离根最 远)，且v,w两个节点都是u的子孙。 LeetCode 236....Lowest Common Ancestor of a Binary Tree 思考与分析 1.两个节点的公共祖先一定在从根节点，至这两个节点的路径上。...2.由于求公共祖先中的最近公共祖先，那么即同时出现在这两条路 径上的离根节点最远的节点(或离两个最近)。 3.最终算法即:求p节点路径，q节点路径，两路径上最后一个相同 的节点。 ?...2.同时遍历p节点的路径与q节点的路径，遍历n个节点，最后一个相同节点，即最近 公共祖先。...if(node_p_path[i] = node_q_path[i]){ result = node_p_path[i]; }//最后相同的节点为最近公共节点

71120

LeetCode 236：二叉树的最近公共祖先

这是无量测试之道的第216篇原创 特别说明： 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点...因为根据定义最近公共祖先节点可以为节点本身。 ---- 解题思路：   一般二叉树相关的算法题，都可以使用递归这个编程技巧来解题，本题也不例外。...先从左子树上找共同的祖先，记为left    2....如果left为nil，则说明要么2个节点都在右子树上，或者至少有一个不在这个二叉树上。 关于递归：    递归这种编程技巧是非常有用的，掌握它，可以为我们解决很多思考起来很麻烦的题目。...后续为了让大家体会到递归编程技巧的强大，我又借二叉树的遍历例子用递归来实现为大家展示递归的强大。大家如果想更好的理解递归的调用栈的话，可以看我自己写的文章：leetcode 递归编程技巧-链表算法题。

27310

LeetCode 二叉树的最近公共祖先(二叉树)

题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。...百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”...= 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。...因为根据定义最近公共祖先节点可以为节点本身。 说明: 所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉树中。...思路 递归自底向上遍历每个节点： 如果此节点为空返回空； 如果此节点为p或q返回该节点； 如果该节点的左孩子或右孩子为p或q，返回该节点的左子树或右子树； 如果该节点左子树为p右子树为q则该节点为最近公共祖先

16510

【LeetCode 236.二叉树的最近公共祖先】双解法：递归实现 + 利用父指针

题目描述：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 解法 1: 递归实现（推荐） 这题相较于 LeetCode 235.二叉搜索树的最近公共祖先 的递归思考起来比较有难度。...封装一个 recurseTree 递归函数，它返回 true/false，代表当前二叉树中是否存在 p、或者存在 q、或者两个节点都存在。...在 recurseTree 递归过程中，如果发现当前二叉树同时存在 p 和 q，那么就更新最近公共祖先。...那么对 node 来说，它的所有祖先节点就是从 node 开始，一直向上遍历父亲节点，统计过程中所有经历的节点，这些节点组成的集合就是所有祖先节点。...整体思路如下： 遍历二叉树，直到 p 和 q 都被遍历完 统计 p 的所有祖先节点，放入集合 set 中 从 q 开始，不断向上访问祖先节点，每次都检查节点是否在集合 set 中 代码实现如下： //

28440

Day19-二叉树-最近公共祖先

Q：已知一个二叉树，给定两个节点，求这两个节点的最近公共祖先 举例：网上找一张图 ?...5，0的最近公共祖先，就是3，根节点 5，4的最近公共祖先，就是5 7，4的最近公共祖先，就是2 三 冷静分析 其实有了昨天的题，是做了很好的铺垫的。...逻辑比较简单，我直接说了啊 1.首先我们需要知道，两个节点的公共祖先，一定在，从根节点到这两个节点的路径上。...举例： 节点7的路径：3 -> 5 -> 2 -> 7 节点4的路径：3 -> 5 -> 2 -> 4 长度一样，同时遍历两个路径，当发现最后的相同的节点，即2，就是最近公共祖先了 四 完整代码及注释...root || finish){//用finish来标识是否找到了待搜索节点，以免不必要的递归 return; } path.push_back(root);

87510

LeetCode-236-二叉树的最近公共祖先

# LeetCode-236-二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。...百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”...5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。...因为根据定义最近公共祖先节点可以为节点本身。 说明: 所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉树中。...= null) { return root;//如果左右都存在，就说明pq都出现了，这就是，公共祖先，此时不用考虑公共祖先是自己的情况，因为上面已经做过判断了。

23020

二叉树的最近公共祖先

题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。...百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”...二叉搜索树的最近公共祖先 《剑指Offer》同题：面试题68 - II. 二叉树的最近公共祖先 《程序员面试金典》同题：面试题 04.08. 首个共同祖先 2....解题 如果左右子树都找到了，就返回root 如果只有一边找到就返回非空的那边 如果都没有找到就返回NULL 递归查找 ?...NULL;//返回NULL if(left && right)//左右都找到了p,q，root就是答案 return root; else//一遍找到了p,q，返回找到的那边

42230

二叉树的最近公共祖先

二叉树的最近公共祖先题解集合 DFS BFS 总结 ---- DFS 对于二叉树中某两个节点的最近公共祖先，存在两种情况: 1.分别位于两个不同的子树中 首先，我们知道递归处理的是规模不同...，问题相同的事情，这里情况1中 规模不同是处理的每颗二叉树的大小不同， 问题相同指的是都是找当前二叉树的左右子树的根节点为最近的公共祖先 2.位于同一颗子树中 同上可知，这里处理的也是规模不同，...问题相同的事情 既然都是规模不同，问题相同，那就可以用递归解决 那么用递归解决的思路是什么呢?...当前节点即为最近公共祖先； 如果左右子树其中一个不为空，则返回非空节点，此时返回的非空节点就是最近工作祖先，如果左右子树其中一个为空，则表示当前子树中不存在p和q节点 这里对上面的思路进行画图解释一波:...二叉树的最近公共祖先一模一样的原题

22510

二叉树的最近公共祖先 II

题目 给定一棵二叉树的根节点 root，返回给定节点 p 和 q 的最近公共祖先（LCA）节点。 如果 p 或 q 之一不存在于该二叉树中，返回 null。 树中的每个节点值都是互不相同的。...根据维基百科中对最近公共祖先节点的定义：“两个节点 p 和 q 在二叉树 T 中的最近公共祖先节点是后代节点中既包括 p 又包括 q 的最深节点（我们允许一个节点为自身的一个后代节点）”。...示例 1: 输入： root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出： 3 解释： 节点 5 和 1 的共同祖先节点是 3。...示例 2: 输入： root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出： 5 解释： 节点 5 和 4 的共同祖先节点是 5。...根据共同祖先节点的定义，一个节点可以是自身的后代节点。

30650

二叉树的简单实战 → 一起温故下二叉树的遍历

前情回顾 　　对二叉树的遍历还不了解的，先去看看：二叉树的遍历 → 不用递归，还能遍历吗 　　简单来说，深度遍历用 栈 辅助实现，广度遍历用 队列 辅助实现 　　不管是递归（系统栈）实现，还是 栈...严格来时，是满二叉树的中序遍历） 　　很简单，直接看代码 　　这题很容易，只要你去实操折纸，找到了规律，代码实现就是手到擒来 　　最低公共祖先 　　求同一棵二叉树中两个节点的最低公共祖先节点 　　什么是最低公共祖先...，节点往上向根节点移动，两个节点最先汇聚的节点则是这两个节点的最低公共祖先，例如 　　10 和 4 的最低公共祖先就是 3 　　简单的做法是借助哈希表 　　先遍历一次二叉树，记录所有节点的父节点（HashMap...中 　　一旦找到，这直接返回该节点，就是 n1 与 n2 的最低公共祖先 　　我们来看代码 　　很好理解，也很好实现，就是有点费空间 　　还有一种方式，实现非常简单，但却不好理解，是前辈们反复提炼之后得到的一种解法...总结 　　1、二叉树的遍历是解二叉树题的基础，基础一定要打牢 　　　　相信大家已从上述几个案例中感觉到了 　　　　基础不牢，地动山摇，你们懂的 　　2、举的案例有限，目的也仅仅只是给大家找找感觉

26620

golang刷leetcode 二叉树（10）最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。...百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”...百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”...因为根据定义最近公共祖先节点可以为节点本身。 说明: 所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉树中。...解题思路： 1，如果左子树包含p，右子树包含q，说明，根即为解 2，如果p，q均在左子树，则递归左子树 3，若p，q均在右子树，则，递归右子树 /** * Definition for TreeNode

19410

二叉树的最近公共祖先 IV

题目 给定一棵二叉树的根节点 root 和 TreeNode 类对象的数组（列表） nodes，返回 nodes 中所有节点的最近公共祖先（LCA）。...数组（列表）中所有节点都存在于该二叉树中，且二叉树中所有节点的值都是互不相同的。...我们扩展二叉树的最近公共祖先节点在维基百科上的定义：“对于任意合理的 i 值， n 个节点 p1 、 p2、…、 pn 在二叉树 T 中的最近公共祖先节点是后代中包含所有节点 pi 的最深节点（我们允许一个节点是其自身的后代...示例 1: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [4,7] 输出: 2 解释: 节点 4 和 7 的最近公共祖先是 2。...示例 2: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [1] 输出: 1 解释: 单个节点的最近公共祖先是该节点本身。

36650
点击加载更多

扫码

添加站长 进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

更多标签

活动推荐

    运营活动

    活动名称
    广告关闭

    腾讯云开发者

    扫码关注腾讯云开发者

    扫码关注腾讯云开发者

    领取腾讯云代金券

    热门产品

    热门推荐

    更多推荐

    Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有

    深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

    腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287

    领券