宝鸡做网站公司/北京优化推广公司

题目

算法思想 ：题目提示递归和迭代两种方法，是告诉我们这道题目可以用深度优先搜索和广度优先搜索两种方法。

（1）深度优先搜索 DFS

          我们主要用递归实现，比较简单。开始搜索根的左右子树，搜索到第三层及以后的时候我们要注意除了判断节点值val是否相等以外，继续向下搜索的时候要搜索 （左边子树的左节点和右边子树的右节点） && （左边子树的右节点和右边子树的左节点）

bool dfs(TreeNode* p,TreeNode* q)
{
    if(p == NULL && q == NULL)
        return true;
    if(p == NULL)
        return false;
    if(q == NULL)
        return false;
    if(p != NULL && q != NULL)
         if(p->val == q->val)
             return (dfs(p->left,q->right) && dfs(p->right,q->left) );
         else
             return false;
    return true;
}
bool isSymmetric(TreeNode* root) {
    if(root == NULL)
        return true;
    return dfs(root->left,root->right); 
}

（2） 广度优先搜索 BFS

           这个搜索方式主要是我们一层一层的判断，所以我们定义两个队列存放左右子树的搜索过程。值得注意的是左边子树入队的时候先插入左节点再插入右节点，右边子树先插入右边节点再插入左边节点。我们把队列的队首节点出队的时候，把它的左右子树插入到队尾，循环结束条件就是队列都为空。

 bool bfs(TreeNode* root)
{
    TreeNode* l,*r;
    queue<TreeNode*> a,b;
    a.push(root->left);
    b.push(root->right);
    while(!a.empty() && !b.empty())
    {
        l = a.front();
        r = b.front();
        if(l == NULL && r == NULL)
        {
            a.pop();
            b.pop();
            continue;
        }
        if(l == NULL)
            return false;
        if(r == NULL)
            return false;
        if(l->val != r->val)
            return false;
        else
        {
            a.push(l->left);
            a.push(l->right);
            a.pop();
            b.push(r->right);
            b.push(r->left);
            b.pop();
        }
    }
    return true;
}
bool isSymmetric(TreeNode* root) {
    if(root == NULL)
        return true;
    return bfs(root); 
}