题解 | #二叉树中找到两个节点的最近公共祖先#dfs/递归
在二叉树中找到两个节点的最近公共祖先
https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116
func lowestCommonAncestor( root *TreeNode , o1 int , o2 int ) int {
//1. dfs得到根节点到两个target的路径，最后一个同路径节点就是最近公共祖先
// var flag = false
// var dfs func(root *TreeNode, path *[]int, target int )
// dfs = func(root *TreeNode, path *[]int, target int){
// if root==nil || flag ==true{
// return
// }
// *path = append(*path, root.Val)
// if root.Val==target{
// flag = true
// return
// }
// dfs(root.Left, path, target)
// dfs(root.Right, path, target)
// if flag{
// return
// }
// *path = (*path)[:len(*path)-1]
// }
// path1, path2 := []int{}, []int{}
// dfs(root, &path1, o1)
// flag = false
// dfs(root, &path2, o2)
// ans := -1
// for i,j := 0,0;i<len(path1) && j<len(path2);i,j = i+1,j+1{
// if path1[i]==path2[j]{
// ans=path1[i]
// }else{
// break
// }
// }
// return ans
//2.
if root==nil{
return -1
}
if root.Val==o1 || root.Val==o2{//该节点是其中一个o
return root.Val
}
left := lowestCommonAncestor(root.Left, o1, o2) //寻找左子树
right := lowestCommonAncestor(root.Right, o1, o2)//寻找右子树
if left==-1{ //左子树没有，在右子树中
return right
}
if right==-1{//右子树没有，左子树中
return left
}
return root.Val//两边都非空，则当前节点是祖先
}
