LeetCode题解：对称二叉树

题目描述

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

示例

image.png

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

算法思路

此问题可以采用递归和迭代两种犯法，但两种方法的思路基本相同。
我们要判断是否为对称二叉树，其实就只考虑三方面即可：
1、首先就是比较当前两方节点的值；
2、节点的移动：左子树的左节点与右子树的右节点，左子树的右节点与右子树的左节点进行比较；
3、当左右节点同时遍历完，则是对称二叉树，否则如果其中一方先为null那么不是对称二叉树。

方法一：递归

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

方法二：迭代

使用队列时需要注意推入的顺序（如，左子树的左节点后面跟着右子树的右节点）。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }
    public boolean check(TreeNode p,TreeNode q){
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(p);
        que.offer(q);
        while(!que.isEmpty()){
            TreeNode u = que.poll();
            TreeNode v = que.poll();
            if(u==null&&v==null){
                continue;
            }
            if((u==null||v==null)||(u.val!=v.val)){
                return false;
            }
            que.offer(u.left);
            que.offer(v.right);
            
            que.offer(v.left);
            que.offer(u.right);
        }
        return true;
    }
}