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

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


	return dfs(root, o1, o2).Val
}

func dfs(root *TreeNode, o1, o2 int) *TreeNode {

	if root == nil || root.Val == o1 || root.Val == o2 {
		return root
	}

	left := dfs(root.Left , o1, o2)
	right := dfs(root.Right, o1, o2)
 //如果left为空，说明这两个节点在root结点的右子树上，我们只需要返回右子树查找的结果即可
	if left == nil {
		return right
	}
	// 同上
	if right == nil {
		return left
	}
  //如果left和right都不为空，说明这两个节点一个在root的左子树上一个在root的右子树上，
   //我们只需要返回cur结点即可。
	return root
}