对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的:

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

通过此题掌握树的知识和递归的运用

题目分析：题目的意思是给出一棵二叉树，判断是否是镜像对称，二叉树的镜像对称的定义为二叉树——二叉树轴对称。

我们需要考虑：二叉树为空，返回true；二叉树不为空，则去比较它的左子树和右子树，判断左子树和右子树对应位置上的值是否相等；很显然，我们会运用到递归处理。

代码实现：

public static class TreeNode
{
   int data;
   TreeNode left;
   TreeNode right;

   TreeNode(int val) {
       data = val;
   }
}

public boolean isSymmetric(TreeNode root)
{
   if (root == null)
       return true;
   return checkIsSymmetric(root.left, root.right);
}

public static boolean checkIsSymmetric(TreeNode leftNode, TreeNode rightNode)
{
   if (leftNode == null && rightNode == null)
       return true;
   if ((leftNode == null && rightNode != null) || (leftNode != null && rightNode == null))
       return false;
   if (leftNode.data != rightNode.data)
       return false;
   return checkIsSymmetric(leftNode.left, rightNode.right) && checkIsSymmetric(leftNode.right, rightNode.left);
}

此算法：我们先判断二叉树是否为空，为空，这返回true；不为空，我们就去比较它的左子树和右子树，若左子树和右子树有一个为空，另一个不为空，显而易见返回false；若左子树和右子树有都不为空，则比较左子树和右子树对应的值是否相等，不相等则返回false；之后，我们就可以运用递归，递归左子树和右子树，直至结束。

主函数：

public static void main(String[] args)
{
   TreeNode p = new TreeNode(1);
   p.left = new TreeNode(2);
   p.right = new TreeNode(2);
   p.left.left = new TreeNode(3);
   p.right.right = new TreeNode(3);

   TreeNode q = new TreeNode(1);
   q.left = new TreeNode(2);
   q.right = new TreeNode(2);
   q.left.right = new TreeNode(3);
   q.right.right = new TreeNode(3);

   Tree9 t = new Tree9();
   System.out.println(t.isSymmetric(p));
   System.out.println(t.isSymmetric(q));

}

这里我们在主函数里构造的两棵二叉树如图所示：

P:

    1
   / \
  2   2
 /     \
 3      3

q:

    1
   / \
  2   2
   \   \
   3    3

结果显示：

true
false