二叉搜索树代码的最低共同祖先不通过

Question

有人能帮我处理这段代码吗？我不知道我被挡在哪里了。

给定一个二进制搜索树（BST），在BST中找到两个给定节点的最低公共祖先（LCA）。

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
   TreeNode* res=NULL;
   int i=0;
   postTrav(root,p,q,res,i);
   return res;
}
void postTrav(TreeNode* root, TreeNode* p, TreeNode* q,TreeNode* res,int& i){
    if(!root){
        return;
    }
    postTrav(root->left,p,q,res,i);
    postTrav(root->right,p,q,res,i);
    if(root==p||root==q){
        i++;
    }
    if(i==2){
        res=root;
        i++;
    }
}

Answer 1

除此之外，您可能还有一个逻辑错误，但是，由于C[我假设]是按值调用的，因此设置res和i被更改为给定函数调用的本地设置，但随后被丢弃。您需要传递一些地址，如下所示。特别要注意的是，res现在是postTrav中的TreeNode **。

TreeNode *
lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
{
    TreeNode *res = NULL;
    int i = 0;
    postTrav(root, p, q, &res, &i);
    return res;
}
void
postTrav(TreeNode *root, TreeNode *p, TreeNode *q, TreeNode **res, int *i)
{
    if (!root) {
        return;
    }
    postTrav(root->left, p, q, res, i);
    postTrav(root->right, p, q, res, i);
    if (root == p || root == q) {
        *i++;
    }
    if (*i == 2) {
        *res = root;
        *i++;
    }
}

---

更新：

上面的代码很好。但是，每当我有一个函数需要[并行]返回或维护两个或多个值时，我使用的一种技术是创建一个额外的"遍历"或"帮助器"结构，以简化参数传递。

如果您需要一个需要在调用中修改/维护的额外变量，而不是向所有函数添加一个额外的参数，那么只需向结构中添加另一个变量就会变得很容易。当你在前进的过程中建立自己的逻辑时，这种方法尤其有效。

这是改进的代码。请注意，需要推送/弹出的参数更少。而且，它的执行速度可能与原来的一样快或更快。此外，对我来说，trav->res似乎比*res 干净一点

// traversal "helper" struct
struct _traverse {
    TreeNode *p;                        // not modified
    TreeNode *q;                        // not modified
    TreeNode *res;                      // result
    int i;                              // depth
    // add more variables here as desired ...
#ifdef WANT_TRAVERSAL_STATISTICS
    int visited_count;                  // number of nodes we visited
#endif
};
typedef struct _traverse Traverse;
TreeNode *
lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
{
    Traverse trav;
    trav.p = p;
    trav.q = q;
    trav.res = NULL;
    trav.i = 0;
#ifdef WANT_TRAVERSAL_STATISTICS
    trav.visited_count = 0;
#endif
    postTrav(root, &trav);
#ifdef WANT_TRAVERSAL_STATISTICS
    printf("Visited %d Nodesn",trav.visited_count);
#endif
    return trav.res;
}
void
postTrav(TreeNode *root, Traverse *trav)
{
    if (!root) {
        return;
    }
#ifdef WANT_TRAVERSAL_STATISTICS
    trav->visited_count += 1;
#endif
    postTrav(root->left, trav);
    postTrav(root->right, trav);
    if (root == trav->p || root == trav->q) {
        trav->i++;
    }
    if (trav->i == 2) {
        trav->res = root;
        trav->i++;
    }
}

Answer 2

您没有使用BST.的属性。postTrav应该是这样的：

TreeNode* postTrav(TreeNode* root, TreeNode* p, TreeNode* q,)
{
if (root == NULL||p==NULL||q==NULL) return NULL;
int n1=p->data;
int n2=q->data;
while (root != NULL)
{
     // If both n1 and n2 are smaller than root, then LCA lies in left
    if (root->data > n1 && root->data > n2)
       root = root->left;
    // If both n1 and n2 are greater than root, then LCA lies in right
    else if (root->data < n1 && root->data < n2)
       root = root->right;
    else break;
}
return root;

}