题解 | #二叉树中找到两个节点的最近公共祖先#dfs/递归

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//两边都非空，则当前节点是祖先
}