【LeetCode二叉树#04】判断对称二叉树

标签：right return 04 LeetCode que 二叉树 NULL 节点 left

对称二叉树

力扣题目链接(opens new window)

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

思路

本题中，不能单纯去比较左右子节点的是否对称（都有值且不为空）

因为如果按上面那样做的话，到子节点后就肯定是不对称的（对于左半边而言），但整体上看可能还是对称的，仍然满足题意，由此就会出现错误

因此，我们需要比较的是当前左右节点下的外侧和内侧的节点是否对称，如图所示：

上图中，显然整课二叉树是对称的

我们在判断的时候只需将左2节点与右2节点的子节点按内侧与外侧区分，再进行比较即可

代码

递归法

按照递归三步走来：

1、确定递归函数的参数和返回类型

2、确定递归的终止条件

3、处理下一层的递归逻辑

class Solution {
public:
    //确定递归函数的参数和返回值
    bool cmp(TreeNode* left, TreeNode* right){
        //确定终止条件
        //四种情况
        //空节点情况
        //左节点为空，右节点不为空
        if(left == NULL && right != NULL) return false;
        //左节点不为空，右节点为空
        else if(left != NULL && right == NULL) return false;
        //左节点为空，右节点为空
        else if(left == NULL && right == NULL) return true;

        //非空但值不相等情况
        //左右节点均不为空但值不相等
        else if(left->val != right->val)return false;

        //以下是左右节点均不为空且值相等的情况
        //启用递归去判断他们的子节点（下一层）是否满足对称
        //处理单层逻辑
        bool outside = cmp(left->left, right->right);//外侧
        bool inside = cmp(left->right, right->left);//内侧
        bool res = outside && inside;
        return res;//记得返回最终结果
    }
    bool isSymmetric(TreeNode* root) {
        //判断根节点是否为空
        if(root == NULL) return 0;
        return cmp(root->left, root->right);
    }
};

迭代法

定义两个节点，同时放入 队列 中，然后同时取出判断是否相等，直到遍历结束

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        //创建队列
        queue<TreeNode*> que;
        //判断根节点是否为空，为空直接对称
        if (root == NULL) return true;
        //获取左右节点（相对于root来说的）
        //加入队列
        que.push(root->left);
        que.push(root->right);

        //队列不为空则遍历
        while(!que.empty()){
            //取出队列中的两个节点
            TreeNode* left = que.front();
            que.pop();
            TreeNode* right = que.front();
            que.pop();
            // //左节点为空，右节点有值//左节点有值，右节点为空//左右节点有值但不同
            // if(left == NULL && right != NULL || left != NULL && right == NULL || left->val != right->val){
            //     return false;
            // }else if(left == NULL && right == NULL){
            //     continue;
            // }
            //左右节点均为空
            if(left == NULL && right == NULL){
                continue;
            }

            //队列中如果没有同时放入两个节点就直接代表不对称了，即有一个为空就可以下判断
            //其实还是对应之前的三种情况，只是在队列中表现方式不同
            if((right == NULL || left == NULL|| (left->val != right->val))){
                return false;
            }
            //排除上面的情况后就剩下不为空且对称的情况
            
            
            //继续加入当前左右节点的子节点,依旧遵循内外侧原则
            //外侧
            que.push(left->left);
            que.push(right->right);
            //内侧
            que.push(left->right);
            que.push(right->left);
        }
        //完成上述遍历没返回false就是对称的
        return true;
    }
};

注意点

1、因为已经使用了队列，每次我们都需要放入两个节点，如果某次发现取的时候只有一个，那直接就可以判定当前情况为不对称‘

标签：right,return,04,LeetCode,que,二叉树,NULL,节点,left
From： https://www.cnblogs.com/DAYceng/p/17146399.html