最小公共祖先知识点

暴力解法

int lca(int x,int y){
	if(x == y){
		return x;
	}
	else if(depth[x] == depth[y]){//fa[i]为i节点的父节点
		return lca(fa[x],fa[y]);
	}
	else if(depth[x] < depth[y]){
		return lca(x,fa[y]);
	}
	else{
		return lca(fa[x],y);
	}
}

二叉搜索树

Node* FindLowestCommonAncestor(Node* root, Node* n1, Node* n2)
{
    //参数有一个为空返回NULL
    if (root == NULL || n1 == NULL || n2 == NULL)
        return NULL;

    if (root->data > n1->data && root->data > n2->data)//root > n1,n2
        return FindLowestCommonAncestor(root->left, n1, n2);
    else if (root->data < n1->data && root->data < n2->data)//root < n1,n2
        return FindLowestCommonAncestor(root->right, n1, n2);
    else//n < root < n
        return root;
}

不给出父结点的树

//判断某个结点在当前树中
bool IsInTheBinaryTree(Node* root, Node* n)
{
    if (root == NULL || n == NULL)
        return false;
    if (root == n)
        return true;
    bool found = IsInTheBinaryTree(root->left, n);
    if (!found)
        found = IsInTheBinaryTree(root->right, n);
    return found;
}


Node* FindLowestCommonAncestor(Node* root, Node* n1, Node* n2)
{
    //参数有一个为空返回NULL
    if (root == NULL || n1 == NULL || n2 == NULL)
        return NULL;
    //都在左子树，结果必在左子树中
    if (IsInTheBinaryTree(root->left, n1) && IsInTheBinaryTree(root->left, n2))
        return FindLowestCommonAncestor(root->left, n1, n2);
    //都在右子树，结果必在右子树中
    else if (IsInTheBinaryTree(root->right, n1) && IsInTheBinaryTree(root->right, n2))
        return FindLowestCommonAncestor(root->right, n1, n2);
    else
        return root;
}

优化：保存从根节点到给定树结点的路径

bool GetPath(Node* root, Node* n, vector<Node*>& v)
{
    if (root == NULL || n == NULL)
        return false;
    if (root == n)
    {
        v.push_back(root);
        return true;
    }
    v.push_back(root);

    bool found = false;
    found = GetPath(root->left, n, v);

    if (!found)
        found = GetPath(root->right, n, v);

    if (!found)
        v.pop_back();
    return found;
}



Node* FindLowestCommonAncestor(Node* root, Node* n1, Node* n2)
{
    //参数有一个为空返回NULL
    if (root == NULL || n1 == NULL || n2 == NULL)
        return NULL;
    vector<Node*> v1;
    bool hasPath1 = GetPath(root, n1, v1);
    vector<Node*> v2;
    bool hasPath2 = GetPath(root, n2, v2);

    if (hasPath1 && hasPath2)
    {
        int i = 0;
        while (v1[i] == v2[i])
        {
            ++i;
        }
        return v1[i - 1];
    }
    else
    {
        return NULL;
    }

}