判断对称二叉树

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

例如，二叉树 [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

 

package com.loo;

import java.util.Queue; import java.util.LinkedList;

public class SymmetricTree {     public static void main(String[] args) {         TreeNode root = new TreeNode(8);         TreeNode l1 = new TreeNode(4);         TreeNode l2 = new TreeNode(2);         TreeNode l3 = new TreeNode(5);         TreeNode r1 = new TreeNode(4);         TreeNode r2 = new TreeNode(2);         TreeNode r3 = new TreeNode(5);         root.left = l1;         l1.left = l2;         l1.right = l3;         root.right = r1;         r1.left = r3;         r1.right = r2;         System.out.println(isSymmetricTree1(root));         System.out.println(isSymmetricTree2(root));     }

    static class TreeNode {         int value;         TreeNode left;         TreeNode right;         public TreeNode(int v) {             value = v;         }     }

    public static boolean isSymmetricTree1(TreeNode root) {         if (root == null) {             return true;         }         return checkSymmetricTree1(root , root);     }

    public static boolean checkSymmetricTree1(TreeNode p , TreeNode q) {         if (p==null && q==null) {             return true;         }         if (p==null || q==null) {             return false;         }         return p.value == q.value && checkSymmetricTree1(p.left , q.right) && checkSymmetricTree1(p.right , q.left);     }

    public static boolean isSymmetricTree2(TreeNode root) {         if (root == null) {             return true;         }         return checkSymmetricTree2(root , root);     }

    public static boolean checkSymmetricTree2(TreeNode p , TreeNode q) {         Queue<TreeNode> queue = new LinkedList<TreeNode>();         queue.offer(p);         queue.offer(q);         while (!queue.isEmpty()) {             p = queue.poll();             q = queue.poll();             if (p==null && q==null) {                 continue;             }             if (p==null || q==null || p.value != q.value) {                 return false;             }             queue.offer(p.left);             queue.offer(q.right);             queue.offer(p.right);             queue.offer(q.left);         }         return true;     } }