利用了二叉搜索树的特性，这么简单的迭代方式，我会感动得流泪！二叉搜索树的最近共同祖先链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/给定一棵二叉搜索树，找到最近的树中两个指定节点的共同祖先。百度百科对最近共同祖先的定义是：“对于有根树T的两个节点p和q，最近共同祖先表示为节点x，满足x是p和q的祖先，深度为x尽可能大（一个节点也可以是它自己的祖先）。”例如，给定以下二叉搜索树：root=[6,2,8,0,4,7,9,null,null,3,5]示例1：输入：root=[6,2,8,0,4,7,9,null,null,3,5],p=2,q=8输出：6解释：节点2和8的最近共同祖先是6。示例2：输入：root=[6,2,8,0,4,7,9,null,null,3,5],p=2,q=4输出：2解释：最近的节点2和节点4的共同祖先是2，因为根据定义最近的公共祖先节点可以是节点本身。解释：所有节点的值都是唯一的。p和q是不同的节点，都存在于给定的二叉搜索树中。做过二叉树：共同祖先问题的同学应该都知道，用回溯自底向上搜索，如果遇到左子树有p，右子树有q的节点，那么当前节点就是最近的共同祖先.那么这道题就是二叉搜索树，二叉搜索树是有序的，所以你要好好利用这个特性。在一棵有序树中，如果判断一个节点的左子树有p，右子树有q？其实从上到下遍历时只要cur节点的值在区间[p,q]内，就说明节点cur是最近的共同祖先。明白了这一点，问题就容易解决了。与二叉树：共同祖先问题不同，普通二叉树需要使用回溯法寻找最近的共同祖先，自底向上搜索。没有用到二叉查找树，因为查找树是有序的（相当于自己的方向），所以只要从顶层到顶层下遍历就可以了。那么我们就可以使用前序遍历（其实这里没有中间节点的处理逻辑，遍历的顺序无所谓）。如图：p是节点3，q是节点5的二叉查找树的最近公共祖先。可以看出，可以直接按照指定的方向找到节点4，也就是最近公共祖先，不需要遍历整棵树。找到结果直接返回！递归方法的递归三部曲如下：确定递归函数的返回值和参数参数为当前节点，两个节点p，q。返回值是返回最近的共同祖先，所以是TreeNode*。代码如下：TreeNode*traversal(TreeNode*cur,TreeNode*p,TreeNode*q)判断终止条件，遇到null就返回即可。代码如下：if(cur==NULL)returncur;事实上，这个终止条件是不需要的。因为题目说p和q是不同的节点，都存在于给定的二叉搜索树中。也就是说，必须找到共同的祖先，所以不存在空洞的情况。判断单级递归的逻辑是在遍历二叉搜索树的时候找到区间[p->val,q->val]（注意这里是左闭闭闭），那么如果cur->val是大于p->val，同时cur->val大于q->val，则应该向左遍历（说明目标区间在左子树上）。需要注意的是，此时我们并不知道p和q谁大，所以两者都要判断代码如下：if(cur->val>p->val&&cur->val>q->val){TreeNode*left=traversal(cur->left,p,q);if(left!=NULL){returnleft;}}细心的同学会发现这里调用递归函数的地方，递归的返回值函数被留下并直接返回。二叉树中：共同祖先问题，如果递归函数有返回值，如何区分是搜索一条边还是搜索整棵树。搜索一条边：if(递归函数(root->left))return；if(递归函数(root->right))return;搜索整棵树：left=递归函数（root->left）；right=递归函数（root->right）；左右的逻辑处理；这道题是标准的找边的方式，遇到递归函数的返回值，如果不为空，就立即返回。如果cur->val小于p->val，cur->val小于q->val，那么应该向右遍历（目标区间在右子树）。if(cur->val
