验证二叉树是否为对称二叉树，即左子树和右子树是否对称。
如下面两个二叉树，左边的为对称二叉树，右边的为非对称二叉树。
方法一：可以先把其中一个子树翻转，然后对比两个子树是否相同
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; }