# Symmetric Tree

<https://leetcode.com/problems/symmetric-tree/description/>

> Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

## Thoughts

不难想到对每层检查是否是对称的。 需要注意的是要把null也考虑到。 还有就是dfs解法，同时追踪两个点，以root的左右两点为起始，可以观察到每次往下递归都要两个点相等且node1的左(右)和node2的右（左）相等。

## Code

```
class Solution {

    public boolean isSymmetric(TreeNode root) {

        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int length = queue.size();
            TreeNode[] nodes = new TreeNode[length];
            for (int i = 0; i < length; i++) {
                TreeNode node = queue.remove();
                nodes[i] = node;
                if (node != null) {
                    queue.add(node.left);
                    queue.add(node.right);
                }
            }

            for (int i = 0, j = length - 1; i < j; i++, j--) {         
                if (nodes[i] != null && nodes[j] != null && nodes[i].val != nodes[j].val ||
                    nodes[i] == null && nodes[i] != nodes[j] || nodes[j] == null && nodes[i] != nodes[j]) {
                    return false;
                }

            }

        }

        return true;
    }

}


public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmHelper(root.left, root.right);
    }

    private boolean isSymmHelper(TreeNode node1, TreeNode node2) {
        if (node1 == null) {
            return node2 == null? true: false;

        } else if (node2 == null) {
            return false;
        }

        if (node1.val != node2.val) {
            return false;
        }

        return isSymmHelper(node1.left, node2.right) &&
            isSymmHelper(node1.right, node2.left);
    }
}
```

## Analysis

Errors: 1. nodes\[i] == null && nodes\[i] != nodes\[j] 没有写nodes\[i] == null

时间复杂度都是O(n)

### Ver. 2

对两个树同时遍历，方向反着，检查是否同时想等。

```
/**
 * 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 == NULL) return true;
        stack<TreeNode*> l, r;
        if (root->left != NULL) l.push(root->left);
        if (root->right != NULL) r.push(root->right);
        while (!l.empty() && !r.empty()) {
            const auto l_cur = l.top(); l.pop();
            const auto r_cur = r.top(); r.pop();
            if (l_cur->val != r_cur->val) return false;
            if (l_cur->left != NULL) {
                if (r_cur->right == NULL) return false;
                l.push(l_cur->left);
                r.push(r_cur->right);
            }
            if (l_cur->right != NULL) {
                if (r_cur->left == NULL) return false;
                l.push(l_cur->right);
                r.push(r_cur->left);
            }
            if (r_cur->left != NULL && l_cur->right == NULL || r_cur->right != NULL && l_cur->left == NULL) return false;
        }
        if (!l.empty() || !r.empty()) return false;
        return true;
    }
};
```


---

# 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://hao-fu-1.gitbook.io/oj/search/level-order-traversal/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.