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

package main
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 
 * @param root TreeNode类 
 * @param o1 int整型 
 * @param o2 int整型 
 * @return int整型
*/


func lowestCommonAncestor( root *TreeNode ,  o1 int ,  o2 int ) int {
    // write code here
    var parentMap = make(map[int]int, 10)
    traverseTree(parentMap, root, -1)
    o1Parents := make([]int, 0)
    
    cur := o1
    o1Parents = append(o1Parents, cur)
    for {
        if cur == -1 {
            break
        }
        if p, ok := parentMap[cur]; ok {
            o1Parents = append(o1Parents, p)
            cur = p
        } 
    }
    
    cur = o2 
    for {
        if cur == -1 {
            break
        }
        if isInSlice(o1Parents, cur) {
            return cur
        }
        if p, ok := parentMap[cur]; ok {
            cur = p
        } 
    }
   
    return -1
}

func isInSlice(s []int, target int) bool {
    for _, v := range s {
        if v == target {
            return true
        }
    }
    return false
}


func traverseTree(parentMap map[int]int, root *TreeNode, parentVal int ) {
    if root == nil {
        return
    }
    parentMap[root.Val] = parentVal
    if root.Left != nil {
        traverseTree(parentMap, root.Left, root.Val) 
    }
    if root.Right != nil {
        traverseTree(parentMap, root.Right, root.Val) 
    }
}