> For the complete documentation index, see [llms.txt](https://liuyang89116.gitbook.io/my-leetcode-book/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuyang89116.gitbook.io/my-leetcode-book/chapter_3_binary_tree_bfs-_dfs/basics/problem_100_same_tree/problem-101-symmetric-tree.md).

# Problem 101: Symmetric Tree

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

## 思路

* 递归的思路就是判断是否都为空，或者值是否相等；然后就是判断左子树的右边和右子树的左边是否一样，左子树的左边和右子树的右边是否一样
* 递归的函数有时候原方程的结构不合适，需要改写（比如 parameter 的个数不一样）
* 对于非递归解法，用一个 queue 来记录 node 的顺序，然后依次对比。注意在 while 循环的里面，是分两部分来处理的。
* 递归解法

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;

        return helper(root.left, root.right);
    }

    private boolean helper(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;

        if (p == null || q == null) return false;

        return (p.val == q.val) && helper(p.left, q.right) && helper(p.right, q.left);
    }
}
```

* 非递归解法

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null || root.left == null && root.right == null) return true;
        if (root.left == null || root.right == null) return false;

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if (left.val != right.val) return false;

            if (left.left != null && right.right != null) {
                queue.offer(left.left);
                queue.offer(right.right);
            } else if (left.left == null && right.right != null || left.left != null && right.right == null) {
                return false;
            }

            if (left.right != null && right.left != null) {
                queue.offer(left.right);
                queue.offer(right.left);
            } else if (left.right != null && right.left == null || left.right == null && right.left != null) {
                return false;
            }
        }

        return true;
    }
}
```