题解 | #在二叉树中找到两个节点的最近公共祖先# go

在二叉树中找到两个节点的最近公共祖先

http://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116

go

/**
 * 
 * @param root TreeNode类 
 * @param o1 int整型 
 * @param o2 int整型 
 * @return int整型
*/
func lowestCommonAncestor( root *TreeNode ,  o1 int ,  o2 int ) int {
    // write code here
    if root == nil {
        return -1
    }

    var isParent func(root *TreeNode ,  o1 int ,  o2 int) *TreeNode
    isParent = func(root *TreeNode, o1, o2 int) *TreeNode {
        if root == nil {// 遇到null,返回null 没有LCA
            return root
        }
        // 遇到o1或o2,直接返回当前节点
        if root.Val == o1 || root.Val == o2 {
            return root
        }

         // 非null 非o1 非o2,则递归左右子树
        left := isParent(root.Left, o1, o2)
        right := isParent(root.Right, o1, o2)

        // 根据递归的结果,决定谁是LCA
        if left == nil {
            return right
        }
        if right == nil {
            return left
        }

        return root
    }


    node := isParent(root, o1, o2)
    if node != nil {
        return node.Val
    }
    return -1
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-08 10:39
一个证都没 我能填什么
程序员小白条:别人有,你为什么没有,还是这个道理,社会就是比较,竞争,淘汰,你要安逸,那么就要做好淘汰的准备
点赞 评论 收藏
分享
测试糕手手:社会第一课,随便吹牛逼,直接说四个月,别老实。老实人只会被欺负
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
码农索隆:想看offer细节
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 15:36
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务