题解 | #二叉搜索树的最近公共祖先#

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
	if q < p {
		p, q = q, p
	}

	if q < root.Val {
		return lowestCommonAncestor(root.Left, p, q)
	}

	if p > root.Val {
		return lowestCommonAncestor(root.Right, p, q)
	}
	
	return root.Val
}

首先，题目不需要考虑异常情况，如节点不存在，节点值重复等，因此程序无需返回-1、0这种兜底逻辑的值。

其次，这是一颗二叉搜索树，小的节点在左，打的节点在右，因此，对输入的p、q进行排序，p为较小的值，q为较大的值，如果q小于当前节点值（因p<q，此时p也小于），则向左递归搜索，如果p大于当前节点值（因p<q，此时q也大于），则向右递归搜索，如果p和q在当前节点两侧，则当前节点为最近公共祖先。