Same Tree--LeetCode

题目：

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

思路：使用递归，如果不使用递归，也可以按照相同的遍历方法，记录遍历的节点，比较两个遍历的节点

bool SameTree(BinTree* first,BinTree* second)
{
    if(first==NULL && second == NULL)
        return true;
    else if(first != NULL && second == NULL)
        return false;
    else if(first == NULL && second !=NULL)
        return false;
    else
    {
        if(first->value != second->value)
            return false;
        else
            return SameTree(first->left,second->left)&&SameTree(first->right,second->right);
    }
}

不使用递归也是可以解决问题的，可以考虑使用层次遍历的方法，层次遍历方法比较两个树是否相同。

bool SameTree(BinTree* first,BinTree* second)
{
    deque<BinTree*> vec;
    deque<BinTree*> sec;
    int i;
    vec.push_back(first);
    sec.push_back(second);
    BinTree* temp,*temp1 ;
    while(!vec.empty() && !sec.empty())
    {
        temp = vec.front();
        vec.pop_front();
        temp1 = sec.front();
        sec.pop_front();
        if(temp != NULL && temp1 != NULL && temp->value == temp1->value)
        {
            if(temp->left != NULL)
                vec.push_back(temp->left);
            else if(temp1->left != NULL)
                return false;
            if(temp->right != NULL)
                vec.push_back(temp->right);
            else if(temp1->right != NULL)
                return false;
            if(temp1->left != NULL)
                sec.push_back(temp1->left);
            else if(temp->left != NULL)
                return false;
            if(temp1->right != NULL)
                sec.push_back(temp1->right);
            else if(temp->right != NULL)
                return false;
        }
        else
            return false;
    }
    if(!vec.empty() || !sec.empty())
        return false;
    return true;
}