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

简单容易写

思路：非递归，利用二叉搜索树的特点。左子树<根节点<右子树

• 若p,q都比当前结点的值小，说明最近公共祖先结点在当前结点的左子树上，继续检查左子树；
• 若p,q都比当前结点的值大，说明最近公共祖先结点在当前结点的右子树上，继续检查右子树；
• 若p,q中一个比当前结点的值大，另一个比当前结点的值小，则当前结点为最近公共祖先结点

复杂度分析：基于二叉搜索策略，故时间复杂度O(log n)，空间复杂度O(1)

public int lowestCommonAncestor (TreeNode root, int p, int q) {
		TreeNode curnode=root;//当前遍历结点
		while(true) {
			if(p<curnode.val&&q<curnode.val) curnode=curnode.left;//在左子树找
			else if(p>curnode.val&&q>curnode.val) curnode=curnode.right;//在右子树找
			else return curnode.val;
		}
	}