题解 | #农场牛群族谱#

知识点：

二叉树的遍历

解题思路：

递归的判断当前节点的左右子树是否存在p,q，终止条件是root == nil || root.Val == q || root.Val == p

语言：

Golang

package main
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
    res := traversal(root, p,q)
    return res.Val
}
func traversal( root *TreeNode ,  p int ,  q int) *TreeNode{
    if root == nil || root.Val == q || root.Val == p{
        return root
    }
    left:=traversal(root.Left,p,q)
    right:=traversal(root.Right, p,q)
    if left!=nil && right!=nil{
        return root
    }else if right !=nil {
        return right
    }else if left!=nil{
        return left
    }
    return nil
}