判断两颗二叉树是否相似的两种方法

//层次遍历法判断两棵树是否相似bool IsSemblable1(BiTree T1,BiTree T2){  stack<BiTNode* > _sta1,_sta2;  //用来存放下一层元素的容器，此处栈和队列都行  BiTNode *p1 = T1,*p2 = T2;   //p1用来跟踪T1,p2用来跟踪T2  while((_sta1.empty() == false || p1 != NULL) &&(_sta2.empty() == false || p2 != NULL))  {    if(p1 != NULL && p2 != NULL )  //如果p1和p2都不为空时    {      if(p1->lchild != NULL && p2->lchild != NULL)  //如果p1和p2的左子树都不为空时      {        _sta1.push(p1->lchild);        _sta2.push(p2->lchild);      }      else if( p1->lchild != NULL || p2->lchild != NULL)  //如果p1的左子树为空，但是p2的左子树不为空，或者相反        return false;      if(p1->rchild != NULL && p2->rchild != NULL)   //如果p1和p2的右子树都不为空时      {        _sta1.push(p1->rchild);        _sta2.push(p2->rchild);      }      else if(p1->rchild != NULL || p2->rchild != NULL)  //如果p1的右子树为空，但是p2的右子树不为空，或者相反        return false;      //访问完两棵树的当前结点后，置空让下一次循环弹出栈中元素（此处其实直接弹出元素也行）      p1 = NULL;      p2 = NULL;    }    else if(p1 != NULL || p2 != NULL)    //当前节点有一个为空      return false;    else    {      //弹出两个树的栈顶元素      p1 = _sta1.top();      p2 = _sta2.top();      _sta1.pop();      _sta2.pop();    }  }  return true;}

//递归判断两棵树是否相似bool IsSemblable2(BiTree T1,BiTree T2){  bool leftS = false,rightS = false;   //用来接受子树返回的信息  if(T1 == NULL && T2 == NULL)    //两个结点都为空    return true;  else if(T1 == NULL || T2 == NULL)  //有一个结点不为空    return false;  else  {    int leftS = IsSemblable2(T1->lchild,T2->lchild);  //递归左子树    int rightS = IsSemblable2(T1->rchild,T2->rchild);  //递归右子树    return leftS && rightS ;  //返回两个子树的信息  }}