LeetCode 101.对称二叉树（DFS、BFS）

快来打我* 2022-12-02 13:47 55阅读 0赞

**上一篇博客：[LeetCode 104.二叉树的最大深度（DFS、BFS）][LeetCode 104._DFS_BFS]**

>  写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。最近萌生了刷LeetCode的想法，所以我打算从LeetCode简单的题目开始做起，攻陷LeetCode。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[LeetCode 101.对称二叉树][LeetCode 101.]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  进阶
 *  题解
 *   *  DFS解法（递归法）
     *   *  解题思路
         *  解题代码
         *  时间复杂度
         *  提交结果
     *  BFS解法
     *   *  解题思路
         *  解题代码
         *  时间复杂度
         *  提交结果

# 题目信息 #

## 题目描述 ##

给定一个二叉树，检查它是否是镜像对称的。  
例如，二叉树 `[1,2,2,3,4,4,3]` 是对称的。  
![示例1][1]  
但是下面这个 `[1,2,2,null,3,null,3]` 则不是镜像对称的:  
![示例2][2]

## 进阶 ##

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

# 题解 #

## DFS解法（递归法） ##

### 解题思路 ###

我们可以使用 `深度优先搜索` 来解决本题，首先我们判断一下根节点是否为空，如果根节点为空，那么证明当前的二叉树为`空树`，默认为对称的二叉树，直接 `return true` 即可。当不为空树时，我们就递归遍历判断该二叉树的 左子树 和 右子树 是否是对称的。

首先我们判断当前遍历到的节点的左孩子和右孩子是否都为空，如果为空说明该二叉树只有一个根节点或者在之后的遍历中我们遇到了叶结点，此时子树是对称的 `return true` 。如果两个节点不都为空或者两个节点的值不相同，说明该树不是对称的，此时 `return false` 。以上是我们递归遍历的结束条件，然后我们递归判断左子树的左孩子和右子树的右孩子以及左子树的右孩子和右子树的左孩子是否相同，如果遍历完整个数没有 `return false` 那么说明该二叉树是对称的，最终会 `return true`。  
![递归][aHR0cHM6Ly9waWMubGVldGNvZGUtY24uY29tLzI0NDlhZjg4NjI1MzdkZjJjYmJjNDVhMDc3NjQ0MTVjMWExMDc2OTY3N2M4MjJmYTI3MWVhNzQ0N2M4ZmExMjgtMi5naWY]

### 解题代码 ###

### 时间复杂度 ###

因为要遍历 **n** 节点，所以时间复杂度为 **O(n)**。

### 提交结果 ###

![提交结果][20200831130032747.png]

## BFS解法 ##

### 解题思路 ###

我们也可以使用 `广度优先搜索` 来解决这个问题，使用一个`队列`进行维护。我们每次将两个在镜像位置的节点入队然后再出队比较两个节点值是否相同，如果相同就继续将在镜像位置的节点入队再继续进行比较。当两个节点不都为空或者两个节点的值不相同时说明不是对称二叉树，此时 `return false` 即可。如果我们遍历完整个二叉树都没有 `return false` 说明该二叉树是对称二叉树。  
![图解2][2 1]

### 解题代码 ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        bool isSymmetric(TreeNode* root) { 
            if (!root || (!root->left && !root->right)) return true;
            return bfs(root, root);
        }
    
        bool bfs(TreeNode* l, TreeNode* r) { 
            queue<TreeNode*> q;
            q.push(l), q.push(r);
            while (!q.empty()) { 
                l = q.front();
                q.pop();
                r = q.front();
                q.pop();
                if (!l && !r) continue;
                if ((!l || !r) || (l->val != r->val)) return false;
    
                q.push(l->left);
                q.push(r->right);
    
                q.push(l->right);
                q.push(r->left);
    
            }
            return true;
        }
    };

### 时间复杂度 ###

与DFS解法相同

### 提交结果 ###

![提交结果][20200831135618430.png]

--------------------

图例来源：[101.对称二叉树 动画演示][101._]

--------------------

> 未完待续，持续更新中……  
> ![冲鸭！][20200831140115933.png]

[LeetCode 104._DFS_BFS]: https://ac-fun.blog.csdn.net/article/details/108308863
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[LeetCode 101.]: https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xoxzgv/
[1]: /images/20221123/fa4a4c5234c0420aa227affaf270f371.png
[2]: /images/20221123/987e72a4db924b199625ff03d9ef7fb9.png
[aHR0cHM6Ly9waWMubGVldGNvZGUtY24uY29tLzI0NDlhZjg4NjI1MzdkZjJjYmJjNDVhMDc3NjQ0MTVjMWExMDc2OTY3N2M4MjJmYTI3MWVhNzQ0N2M4ZmExMjgtMi5naWY]: /images/20221123/e818928a429b4cceb8446d5dff1575e5.png
[20200831130032747.png]: /images/20221123/42dc4d1b68b7433cb3f3bea30d6b64ee.png
[2 1]: /images/20221123/d309c8bf66a8411898266883475ca2e3.png
[20200831135618430.png]: /images/20221123/2023ed737aff483782c985e952e9ebe2.png
[101._]: https://leetcode-cn.com/problems/symmetric-tree/solution/dong-hua-yan-shi-101-dui-cheng-er-cha-shu-by-user7/
[20200831140115933.png]: /images/20221123/5423c630f30249e69fe1043bcd917a97.png