101. 对称二叉树 (opens new window)

解题思路：使用两个指针同时遍历二叉树，两个指针遍历时，左右子树的顺序相反。

第一版

用一个指针遍历两次，两次二叉树遍历的顺序相反，每次遍历都用序列统计当前二叉树的节点值，最后比较两个序列每个位置上的值是否相同。这种方法无论是中序遍历还是后序遍历都难免会有一些特殊情况，比如：[5,4,1,null,1,null,4,2,null,2,null]。而如果是层序遍历，中间的空节点需要额外做处理。

第二版

因此为了排除一些特殊情况，以及子树为空节点，最稳妥的做法就是两个节点同时反序遍历，这样一定能够保证两个节点所指向的TreeNode是对称的位置。写的时候要注意，p和q节点最终都会遍历整个二叉树，因此每个节点不仅要遍历左子树，还要遍历右子树。

遍历时，有如下情况不满足对称：

• 其中一个节点指向的是null
• 两个节点的值不相等
• 两个节点的子树遍历时不满足对称条件

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)||(p!=null&&q==null)) return false;
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);

    }
}