【leetcode】二叉树最近公共祖先

╰半夏微凉° 2022-03-14 14:50 162阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]

--------------------

# 算法思路 #

按照从下面到下面遍历的方法  
如果遍历到p或者q，说明一个在另外一个下面，如实例2：那么直接返回p或者q  
然后往左边和右边遍历  
如果左边和右边都不为空，说明一个在左边一个在右边，那么返回root  
如果其中一个为空，那么返回另外一边。

--------------------

# 代码 #

class Solution:
        def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
            if root == None:
                return None
            if root == p or root == q:
                return root
            left = self.lowestCommonAncestor(root.left, p, q)
            right = self.lowestCommonAncestor(root.right, p, q)
            if left != None and right != None:
                return root
            if left == None:
                return right
            if right == None:
                return left

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220312/dac8b245743f474ab0b1256f22f48370.png

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode236. 二叉树的最近公共祖先

题目难度：中等题目描述： > 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 > p、q，最

你的名字/ 2023年01月22日 12:51/ 0 赞/ 123 阅读

相关 leetcode---236. 二叉树的最近公共祖先(最近公共祖先)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是

矫情吗；*/ 2022年11月28日 00:42/ 0 赞/ 125 阅读

相关 leetcode---235. 二叉搜索树的最近公共祖先（最近公共祖先）

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x

女爷i/ 2022年11月28日 00:42/ 0 赞/ 134 阅读

相关【leetcode236】二叉树的最近公共祖先

题目描述给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。提示：树中节点数目在范围 \[2, 10^5\] 内。 \-10^9<= Node.

一时失言乱红尘/ 2022年11月16日 15:23/ 0 赞/ 131 阅读

相关 leetcode 236 二叉树的最近公共祖先

前言题目：[236. 二叉树的最近公共祖先][236.] 参考题解：[二叉树的最近公共祖先-代码随想录][-] -------------------- 题解代

妖狐艹你老母/ 2022年09月12日 04:50/ 0 赞/ 112 阅读

相关【leetcode】二叉树最近公共祖先

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

╰半夏微凉°/ 2022年03月14日 14:50/ 0 赞/ 163 阅读

相关 leetcode:236. 二叉树的最近公共祖先

题目: 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，

﹏ヽ暗。殇╰゛Y/ 2022年03月02日 03:44/ 0 赞/ 157 阅读

相关 leetcode 236. 二叉树的最近公共祖先

题目描述：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，

小鱼儿/ 2021年10月29日 08:28/ 0 赞/ 230 阅读

相关 leetcode:236. 二叉树的最近公共祖先(dfs 树公共祖先)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 [百度百科][Link 1]中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点

﹏ヽ暗。殇╰゛Y/ 2021年09月28日 11:10/ 0 赞/ 259 阅读

相关 Leetcode-二叉搜索树最近公共祖先

描述：给定一个二叉搜索树，找到该树中两个指定节点的最近公共节点（最近公共祖先节点可以为节点本身）说明：所有节点的值都是唯一的。两个节点为不同节点且存在于给定

梦里梦外;/ 2021年09月23日 14:36/ 0 赞/ 279 阅读