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

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 findCommonAncestor func(node *TreeNode) *TreeNode
	findCommonAncestor = func(node *TreeNode) *TreeNode {
		if node == nil || node.Val == o1 || node.Val == o2 {
			return node
		}
		left := findCommonAncestor(node.Left)
		right := findCommonAncestor(node.Right)
        if left != nil && right != nil {
            return node
        }
        if left != nil {
            return left
        }
        return right
	}
    common := findCommonAncestor(root)
    if common != nil {
        return common.Val
    }
    return -1
}