68.md

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

题目

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 1.对于该题的最近的公共祖先定义:对于有根树T的两个结点p、q，最近公共祖先LCA(T,p,q)表示一个结点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先. 2.二叉搜索树是若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值 3.所有节点的值都是唯一的。 4.p、q 为不同节点且均存在于给定的二叉搜索树中。

示例

输入：{7,1,12,0,4,11,14,#,#,3,5},1,12

返回值：7

说明：节点1和节点12的最近公共祖先是7

思路

• 【划重点】【二叉搜索树】【左 > 跟 > 右】【排序或者判断 nil 都可以】
• 当节点p和节点q都在左子树时，即都小于根节点root时，需要在root的左子树查找其最近公共祖先；
• 当节点p和节点q都在右子树时，即都大于根节点root时，需要在root的右子树查找其最近公共祖先；
• 当节点p和节点q一个在根节点root的左子树，一个在其右子树，或者其中一个节点和根节点相同时，root就是其最近公共祖先

实现

func lowestCommonAncestor(root *TreeNode, p int, q int) int {
	node := core(root, p, q)
	return node.Val
}

// 迭代比较大小
func core(root *TreeNode, p int, q int) *TreeNode {
	if root == nil || p == root.Val || q == root.Val {
		return root
	}
	for root != nil {
		rootVal := root.Val
		if p > rootVal && q > rootVal {
			// 两个节点都在右侧
			root = root.Right
		} else if p < rootVal && q < rootVal {
			// 两个节点都在左侧
			root = root.Left
		} else {
			// 两个节点分别位于左右两侧
			return root
		}
	}
	return nil
}