千家信息网

请输入关键字词

热门搜索排行

最新搜索排行

导航： 首页 > 互联网科技 >

python二叉树中的最近公共祖先是什么

发表于：2026-11-01 作者：千家信息网编辑
千家信息网最后更新 2026年11月01日，python二叉树中的最近公共祖先是什么，针对这个问题，这篇文章详细介绍了相对应的分析和解答，希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。给定一个二叉搜索树, 找到该树中两个指定节点的
千家信息网最后更新 2026年11月01日python二叉树中的最近公共祖先是什么

python二叉树中的最近公共祖先是什么，针对这个问题，这篇文章详细介绍了相对应的分析和解答，希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为："对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。"

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8输出: 6 解释: 节点 和节点 的最近公共祖先是

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4输出: 2解释: 节点  和节点  的最近公共祖先是 , 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。

  • p、q 为不同节点且均存在于给定的二叉搜索树中。

解题思路：

1，利用二叉搜索树的性质：

A，去过p，q最大值小于根节点则，祖先在左子树

B，最小值大于根节点，祖先在右子树

C，祖先是根节点

2，注意p，q的大小未定

/** * Definition for TreeNode. * type TreeNode struct { *     Val int *     Left *ListNode *     Right *ListNode * } */ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {     if root==nil{         return root     }     if p.Val         return lca(root,p,q)     }        return lca(root,q,p)}
func lca(root,p,q *TreeNode)*TreeNode{     if root.Val         return lca(root.Right,p,q)     }     if root.Val>q.Val{         return lca(root.Left,p,q)     }     return root}

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为："对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。"

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出: 3解释: 节点 和节点 的最近公共祖先是节点

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4输出: 5解释: 节点 和节点 的最近公共祖先是节点 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。

  • p、q 为不同节点且均存在于给定的二叉树中。

解题思路：

1，如果左子树包含p，右子树包含q，说明，根即为解

2，如果p，q均在左子树，则递归左子树

3，若p，q均在右子树，则，递归右子树

/** * Definition for TreeNode. * type TreeNode struct { *     Val int *     Left *ListNode *     Right *ListNode * } */ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {      if root==nil || p==nil ||q==nil {        return nil    }     if root.Val==p.Val && root.Val==q.Val{         return root     }     cur:=root     for contain(cur,p)&& contain(cur,q){         if contain(cur.Left,p)&& contain(cur.Left,q){             cur=cur.Left         }else if contain(cur.Right,p)&& contain(cur.Right,q){             cur=cur.Right         }else{             return cur         }     }     return nil     }
func contain(root, p *TreeNode) bool{    if root==nil || p==nil {        return false    }    return root.Val==p.Val || contain(root.Left,p) ||contain(root.Right,p)}

关于python二叉树中的最近公共祖先是什么问题的解答就分享到这里了，希望以上内容可以对大家有一定的帮助，如果你还有很多疑惑没有解开，可以关注行业资讯频道了解更多相关知识。

很赞哦！
节点 祖先 子树 两个 示例 结点 搜索 解释 输入 输出 问题 不同 尽可能 思路 更多 深度 百科 递归 帮助 解答 数据库的安全要保护哪些东西 数据库安全各自的含义是什么 生产安全数据库录入 数据库的安全性及管理 数据库安全策略包含哪些 海淀数据库安全审计系统 建立农村房屋安全信息数据库 易用的数据库客户端支持安全管理 连接数据库失败ssl安全错误 数据库的锁怎样保障安全 苏州找大状互联网科技有限公司 互联网科技有限公司经营范围 互联网扶贫科技 银优互联网科技有限公司 菲比寻常互联网科技 中国最先进互联网科技公司 千方科技属于互联网企业吗 深圳育鹏互联网科技有限公司招聘 西安小鹰速贷互联网科技有限公司 保险科技服务互联网营销体系 锡山区互联网智能科技产品供应 小米互联网科技园入驻 中国互联网有什么科技 广州富喜互联网络科技 皮皮虾互联网科技有限公司 工业互联网科技成果转化 互联网风格科技公司名称 广东鹅鹅鹅互联网科技有限公司 互联网高科技行业有哪些企业 众联互联网络科技 河南云网互联网络科技有限公司 互联网科技的发展 互联网的科技创新 互联网科技英文 无线互联网科技 科技互联网创业计划书 佰商互联网科技有限公司 广州千川互联网科技有限公司 广州互联网高科技取餐柜 株洲百竞科技的互联网营销顾问

相关文章

0