# 101.Symmetric Tree

**101.Symmetric Tree**

难度:Easy

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

```
例如，二叉树 [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
说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
```

递归： 通过一个函数判断，左子树的右孩子和右子树的左孩子，左子树的左孩子和右子树的右孩子应该相等。

```
/**
 * 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 {
bool check(TreeNode* left , TreeNode* right)
{

    if(!left  && !right)return true;
    else if( !left || !right) return false;
    if(left->val != right->val) return false;        
        return check(left->right, right->left) && check(left->left, right->right);
    
}
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        if(!root->left && !root->right) return true;
        return check(root->left, root->right);
        
        
    }
};
```

> 执行用时 :12ms, 在所有 C++ 提交中击败了66.23%的用户\
> 内存消耗 :14.7MB, 在所有 C++ 提交中击败了88.35%的用户

迭代： 创建一个队列来保存二叉树的每个节点，然后比较左节点的右孩子和右节点的左孩子。

```
/**
 * 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) return true;
        if(!root->left && !root->right) return true;
        deque<TreeNode*> t;
        t.push_back(root);
        t.push_back(root);
        while(!t.empty())
        {
            if(!t[0] &&!t[1]) 
            {
                t.pop_front();
                t.pop_front();
                continue;
            }
            if(!t[0] || !t[1]) return false;
            if(t[0]->val != t[1]->val) return false;
            t.push_back(t[0]->left);
            t.push_back(t[1]->right);
            t.push_back(t[0]->right);
            t.push_back(t[1]->left);
            t.pop_front();
            t.pop_front();
        }
        return true;
        
    }
};
```

> 执行用时 :12ms, 在所有 C++ 提交中击败了66.23%的用户\
> 内存消耗 :14.9MB, 在所有 C++ 提交中击败了79.96%的用户


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dfine.gitbook.io/leetcode/101.symmetric_tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.