二叉搜索树的最近公共祖先

func lowestCommonAncestor( root *TreeNode ,  p int ,  q int ) int {
    arr1 := searchNum(root, p)
    arr2 := searchNum(root, q)

    var commonNode int
    for _, v1 := range arr1 {
        for _, v2 := range arr2 {
            if v1 == v2 {
                commonNode = v1
            }
        }
    }

    return commonNode
}

// 找寻目标数，返回查找路径
func searchNum(root *TreeNode, num int) []int {
    arr := []int{}
    for root.Val != num {
        arr = append(arr, root.Val)
        if root.Val > num {
            // 目标数在root节点的左树
            root = root.Left
        } else {
            root = root.Right
        }
    }

    arr = append(arr, num)

    return arr
}

func lowestCommonAncestor( root *TreeNode ,  p int ,  q int ) int {
    // write code here
    tmp:=root
    for{
        if p< tmp.Val && q<tmp.Val{
            tmp=tmp.Left
        }else if p>tmp.Val && q >tmp.Val{
            tmp=tmp.Right
        }else{
            return tmp.Val
        }
    }
}

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func lowestCommonAncestor(root *TreeNode ,  p int ,  q int ) int {
    if root == nil || root.Val == p || root.Val == q {
        return root.Val
    }
    if find(root.Left, p) && find(root.Left, q) {
        return lowestCommonAncestor(root.Left, p, q)
    }
    if find(root.Right, p) && find(root.Right, q) {
        return lowestCommonAncestor(root.Right, p, q)
    }
    return root.Val
}

//前序遍历
func find(root *TreeNode, target int) bool {
    if root == nil {
        return false
    }
    if root.Val == target {
        return true
    }
    return find(root.Left, target) || find(root.Right, target)
}

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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param p int整型 
 * @param q int整型 
 * @return int整型
*/
func lowestCommonAncestor( root *TreeNode ,  p int ,  q int ) int {
    // write code here
    return find(root,p,q).Val
}



func find(root *TreeNode,p ,q int) *TreeNode {
    if root == nil { return nil }
    if root.Val == p || root.Val ==q { return root }
    var left,right *TreeNode
    left = find(root.Left,p,q)
    right = find(root.Right,p,q)
    if left==nil { 
        return right 
    } else if right == nil { return left }
    
    return root
}