给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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，如果都在右子树，递归右子树
代码实现
代码语言：javascript复制/**
* 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，去掉重合部分
代码实现
代码语言：javascript复制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
}
