如何解析python二叉树的最近公共祖先

发布时间:2021-12-13 16:07:30 作者:柒染
来源:亿速云 阅读:159

这篇文章给大家介绍如何解析python二叉树的最近公共祖先,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。

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

百度百科中最近公共祖先的定义为:“对于有根树 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

解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

输出: 5

解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

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

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

解法一:

1,如果两个节点分别在左右子树,返回当前节点

2,如果都在左子树,递归左子树

3,如果都在右子树,递归右子树

代码实现

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */ func lowestCommonAncestor(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode {    if root!=nil && contain(root.Left,p)&& contain(root.Left,q){        return lowestCommonAncestor(root.Left,p,q)    }         if root!=nil && contain(root.Right,p)&& contain(root.Right,q){        return lowestCommonAncestor(root.Right,p,q)    }     return root}func contain(root *TreeNode, p *TreeNode)bool{    if root==nil{        return false    }    if root.Val==p.Val{        return true    }    return contain(root.Left,p)||contain(root.Right,p)}

解法二:

1,找出从根节点到两个点的路径

2,去掉重合部分

代码实现

func lowestCommonAncestor(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode{   var l,r []*TreeNode   _,l=findPath(root,p)   _,r=findPath(root,q)   l=append([]*TreeNode{root},l...)   r=append([]*TreeNode{root},r...)//    for i:=0;i<len(l);i++{//     fmt.Println("l->",l[i].Val)//    }//    for j:=0;j<len(r);j++{//        fmt.Println("r->",r[j].Val)//    }   i:=0   if len(l)==0 ||len(r)==0{       return root   }   for i<len(l)&&i<len(r)&&l[i].Val==r[i].Val{       i++   }   return l[i-1]}
func findPath(root *TreeNode, p *TreeNode)(bool,[]*TreeNode){    var path []*TreeNode    if root==nil{        return false,path    }    if root.Val==p.Val{        return true,path    }    if ok,path:=findPath(root.Left,p);ok{        path=append([]*TreeNode{root.Left},path...)        //fmt.Println(root.Left.Val,"len",len(path))        return true,path    }
   if ok,path:=findPath(root.Right,p);ok{         path=append([]*TreeNode{root.Right},path...)         //fmt.Println(root.Right.Val,"len",len(path))        return true,path    }    return false,path}

关于如何解析python二叉树的最近公共祖先就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。

推荐阅读:
  1. 二叉树找到最近公共祖先示例
  2. java二叉树找到最近公共祖先的方法

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

python 二叉树

上一篇:css如何设置图片放大后隐藏溢出

下一篇:python二叉树的最近公共祖先如何理解

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》