[数据结构与算法]LeetCode101. 对称二叉树 C++

题目描述

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树?[1,2,2,3,4,4,3] 是对称的。

? ? 1
? ?/ \
? 2 ? 2
?/ \ / \
3 ?4 4 ?3
?

但是下面这个?[1,2,2,null,3,null,3] 则不是镜像对称的:

? ? 1
? ?/ \
? 2 ? 2
? ?\ ? \
? ?3 ? ?3
?

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/symmetric-tree

解题思路

用BFS广度优先的方法来层次遍历树，然后进行对比。
看了官方的BFS解法，感觉官方的BFS解法存在点小问题。在对某些孩子结点为NULL的情况下，官方解法都是直接入队。我自己也debug试了一下，但是在取值的时候，push了NULL进去，q.front的值是取不到的，部分编译器下会报空指针异常。所以我自己写了一个，虽然代码有些长，但是比较容易看懂。
1.首先写一个bfs来对两颗树进行判断。首先对根节点特判，如果为空直接return true。
2.然后如果非空，就进入bfs。队列q用来存放层次遍历的结点。当队列不为空时，分别出队两次，因为两棵树需要比较。将其值进行比较，若不相等则直接return fasle。
3.对孩子结点的判断，首先是fasle是四种情况:
r1->left为空，r2->right不空
r1->left不空，r2->right为空
r1->right为空，r2->left不空
r1->right不空，r2->left为空
这四种情况都是不对成的，直接return fasle。
4.除了这四种情况之外，如果相对应的结点都为空，那么不做操作。
5.如果相对应的结点都有值，即对应r1->left!=NULL&&r2->right!=NULL和r1->right!=NULL&&r2->left!=NULL的情况，就入队。
6.如果可以全部走完，那么直接return true。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool bfs(TreeNode* a, TreeNode* b){
        queue<TreeNode*> q; //bfs需要的队列
        q.push(a);  //a的根结点入队
        q.push(b);  //b的根结点入队
        while(!q.empty()){  //队列非空时
            TreeNode* r1=q.front(); //r1用来接受树a的结点，因为a是先入队的，队列的特性是先进先出，所以此时的队头是之前存进去的a的结点。
            q.pop();    //弹出
            TreeNode* r2=q.front(); //同理，r2用来接受树b的结点
            q.pop();    //弹出
            if(r1->val!=r2->val){   //如果当前结点值不相等，直接返回false
                return false;
            }
            //对树a和shub不对称的情况列举
            if((r1->left==NULL&&r2->right!=NULL)    //a左空，b右不空    
            ||(r1->left!=NULL&&r2->right==NULL)     //a左不空，b右空
            ||(r1->right==NULL&&r2->left!=NULL)     //a右空，b左不空
            ||(r1->right!=NULL&&r2->left==NULL)){   //a右不空，b左空
                return false;   //这四种情况结构上就不对称了，所以直接返回false
            }
            //当结构上对称的时候，就来判断值，这边结构上对称中的如果两边都为NULL就直接不做判断。
            if(r1->left!=NULL&&r2->right!=NULL){    // a左和b右结构对称
                q.push(r1->left);   //就全都push进去，在下一轮循环中来判断值是否相等。
                q.push(r2->right);
            }    
            if(r1->right!=NULL&&r2->left!=NULL){    //同理
                q.push(r1->right);
                q.push(r2->left);
            }
        }
        return true;    //如果能全部走完，直接返回true
    }
    bool isSymmetric(TreeNode* root) {
        if(root==NULL){ //特判，空树情况返回true
            return true;
        }
        return bfs(root, root); //否则返回bfs的结果。
    }
};