二叉树：对称树

    验证二叉树是否为对称二叉树，即左子树和右子树是否对称。

    如下面两个二叉树，左边的为对称二叉树，右边的为非对称二叉树。

    方法一：可以先把其中一个子树翻转，然后对比两个子树是否相同

public boolean isSymmetric(TreeNode root) {
    	return isSameTree(root.left, invert(root.right));
    }
    public TreeNode invert(TreeNode root){
    	if(root == null)
    		return null;
    	TreeNode node = root.left;
    	root.left = invert(root.right);
    	root.right = invert(node);
    	return root;
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
	    if(p == null || q == null)
	        return p == q;
	    else if(p != null && q != null){
	        if(p.val != q.val)
	            return false;
        else if(isSameTree(p.left, q.left) && isSameTree(p.right, q.right))
           return true;
	    }
	    return false;
    }
           

    方法二：左子树按照中左右的顺序遍历，右子树按照中右左的顺序遍历，如果每一步访问的值都相同，说明左右子树对称

public boolean isSymmetric(TreeNode root) {
        if(root == null)
            return true;
    	return isSymmetric(root.left, root.right);
    }
    public boolean isSymmetric(TreeNode p, TreeNode q) {
	    if(p == null || q == null)
	        return p == q;
	    if(p.val != q.val)
	        return false;
            return (isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left))//左子树先访问左节点，右子树先访问右节点
    }
           

    方法三：不使用递归，而使用栈（或者队列），把需要比较的两个节点压进栈，再依次比较。

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root.left);
    stack.push(root.right);
    while (!stack.empty()) {
        TreeNode n1 = stack.pop(), n2 = stack.pop();
        if (n1 == null && n2 == null) continue;
        if (n1 == null || n2 == null || n1.val != n2.val) return false;
        stack.push(n1.left);
        stack.push(n2.right);
        stack.push(n1.right);
        stack.push(n2.left);
    }
    return true;
}