LeetCode 热题 100_对称二叉树（39_101_简单_C++）（二叉树；递归；层次遍历（广度优先））

题目描述：

给你一个二叉树的根节点 root ， 检查它是否轴对称。

输入输出样例：

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

题解：

解题思路：

思路一（递归）：

1、我们判断是否为对称二叉树就需要判断对称轴两边的对应结点值和是否相同。
对应结点会存在几种情况：
① 对应结点都为NULL(返回True)
② 对应结点有一个为NULL，另一个不为NULL（返回false）
③ 对应结点val不相等（返回false）
④ 对应结点val相等时，继续判断其他对称结点。
通过上述情况我们可以确定递归出口：分别为①、②、③
递归体为④，通过对应节点的判断也可推出函数的参数有两个，一个是左侧的对应结点，一个是右侧的对应结点。

2、复杂度分析：
① 时间复杂度：O(n)，n代表二叉树中节点的个数，遍历整颗二叉树。
② 空间复杂度：O(n)，与树的高度有关，最高为n。

思路二（层次遍历（广度优先））：

1、可以采用一层一层对应结点的比较，在采用此种比较方法的时候我们优先想到的是使用队列进行存储每层的元素。在用队列存储的时候我们需要将对应结点紧挨着进行存储，这样方便我们比较对应结点。
对应结点会存在几种情况：
① 对称结点都为NULL(继续判断其他结点)
② 对称结点有一个为NULL，另一个不为NULL（返回false）
③ 当对称结点val不相等（返回false）
④ 当对称结点val相等时，继续判断其他对称结点。

2、具体思路如下：
① 创建一个队列存储每层的元素，当左右孩子结点不为空时，放入队列。
② 将此时对应结点出队（出队两个结点），判断其是否满足条件（不是则返回false）。此时将左对应节点的左孩子和右对应结点的右孩子入队，将左对应节点的右孩子和右对应结点的左孩子入队。
③ 重复上述过程，直到发现其为非对称树或队列为空为对称树。

3、复杂度分析
① 时间复杂度：O(n)，n代表二叉树中节点的个数，遍历整颗二叉树。
② 空间复杂度：O(n)，，队列中最多不会超过 n 个结点。

代码实现

代码实现（思路一（递归））：

//方法一递归实现:判断对称二叉树
bool isSymmetric1(TreeNode *root){
    if(root==nullptr) return true;

    return dfs(root->left,root->right);
}

bool dfs(TreeNode *left,TreeNode *right){
    //到达了叶子结点,则返回
    if(left==nullptr&&right==nullptr) return true;
    //排除left和right都为空的情况，若left和right其中一个为空返回false
    if(left==nullptr||right==nullptr) return false;
    //排除空的情况就可以判断结点的值
    if(left->val!=right->val) return false;

    //下面这一行代码是不能加的，会导致代码提前结束
    //if(left->val==right->val) return true;
    return dfs(left->left,right->right)&&dfs(left->right,right->left);
}

代码实现（思路二（层次遍历（广度优先）））：

//方法二层次遍历实现（广度优先）：判断对称二叉树
bool isSymmetric2(TreeNode *root){
	//先对根节点的左右孩子进行判断
    if(root==nullptr||(root->left==nullptr&&root->right==nullptr)) return true;
    //创建队列并将左右孩子入队
    queue<TreeNode *> q;
    q.push(root->left);
    q.push(root->right);
    while (!q.empty())
    {
    	//取两个对应的结点
        TreeNode *left=q.front();
        q.pop();
        TreeNode *right=q.front();
        q.pop();
		//判断是否对称
        if (left==nullptr&&right==nullptr) continue;
        if (left==nullptr||right==nullptr) return false;
        if (left->val!=right->val) return false;
		//将两个节点的对应孩子结点进行入队，注意对应结点紧挨入队
        q.push(left->left);
        q.push(right->right);

        q.push(left->right);
        q.push(right->left);
        
    }
    return true;
}

以思路一为例进行调试

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

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){}

    /* data */
};

class Solution
{
public:
    //创建Tree
    TreeNode *createTree(vector<int> nums){
        if (nums.empty()) return nullptr;
        queue<TreeNode *> q;
        TreeNode *root=new TreeNode(nums[0]);
        q.push(root);
        int i=1;
        while (i<nums.size())
        {
            TreeNode *node=q.front();
            q.pop();
            if(i<nums.size()&&nums[i]!=-1){
                node->left=new TreeNode(nums[i]);
                q.push(node->left);
            }
            ++i;
            if(i<nums.size()&&nums[i]!=-1){
                node->right=new TreeNode(nums[i]);
                q.push(node->right);
            }
            ++i;
        }
        return root;
    }

    //中序遍历输出树
    void inorder(const TreeNode *root){
        if (root==nullptr) return ;
        inorder(root->left);
        cout<<root->val<<" ";
        inorder(root->right);
    }


    //方法一递归实现:判断对称二叉树
    bool isSymmetric1(TreeNode *root){
        if(root==nullptr) return true;

        return dfs(root->left,root->right);
    }

    bool dfs(TreeNode *left,TreeNode *right){
        //到达了叶子结点,则返回
        if(left==nullptr&&right==nullptr) return true;
        //排除left和right都为空的情况，若left和right其中一个为空返回false
        if(left==nullptr||right==nullptr) return false;
        //排除空的情况就可以判断结点的值
        if(left->val!=right->val) return false;

        //下面这一行代码是不能加的，会导致代码提前结束
        //if(left->val==right->val) return true;
        return dfs(left->left,right->right)&&dfs(left->right,right->left);
    }
};



int main(){
    vector<int> nums={1,2,2,-1,3,-1,3};  //1,2,2,3,4,4,3

    Solution s;
    //创建二叉树
    TreeNode *root=s.createTree(nums);
    //中序遍历二叉树（用于验证树是否创建正确）
    // s.inorder(root);

    if(s.isSymmetric1(root)){
        cout<<"是对称二叉树";
    }else{
        cout<<"不是对称二叉树";
    }
    return 0;
}

LeetCode 热题 100_对称二叉树（39_101)原题链接
欢迎大家和我沟通交流(✿◠‿◠)