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

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

在C语言中实现寻找二叉搜索树（BST）中的两个节点p和q的最近公共祖先，可以利用BST的性质来简化问题。由于BST具有左子树上的所有键都小于根节点而右子树上所有的键都大于根节点这一特性，在查找过程中可以根据当前节点值与目标节点值的关系决定向哪个方向移动。

下面是一个基于迭代方法而非递归方式的具体实现方案：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树结构体
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

/// 查找函数：返回给定两节点p,q最低共同父辈指针
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    while (root != NULL){
        // 如果两者均位于当前节点左侧，则往左边走；如果都在右侧则往右边走；
        if ((p->val < root->val && q->val < root->val))
            root = root->left; 
        else if((p->val > root->val && q->val > root->val))  
            root = root->right;
        else break;  // 当前节点即为所求LCA 或者 已经分道扬镳
    }
    
    return root;   
}

此代码片段展示了如何通过比较`p`和`q`相对于当前遍历到的节点的位置关系来进行路径选择，从而最终找到它们之间的最近公共祖先[^2]。