假定用两个一维数组L[n+1]和R[n+1]作为有n个结点的二叉树的存储结构,L[i]和R[i]分别指示节点i（i=1,2,.,n）的左孩子和右孩子,0表示空.试写一个算法判断结点u是否为结点v的子孙.

Question

假定用两个一维数组L[n+1]和R[n+1]作为有n个结点的二叉树的存储结构,
L[i]和R[i]分别指示节点i（i=1,2,.,n）的左孩子和右孩子,0表示空.试写一个算法判断结点u是否为结点v的子孙.

Answer 1

int isGrandChild(int u,int v) //判断u是否为v的子孙
{
if (L[v] == u || R[v] == u) return 1; //1表示是,0表示否
if (L[v] == 0 && R[v] == 0) return 0;
return isGrandChild(u,L[v]) || isGrandChild(u,R[v]); //如果u是L[v]或者R[v]的子孙,那么u也是v的子孙
}