Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1 / 2 2 / \ / 3 4 4 3
But the following is not:
1 / 2 2 \ 3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
题意：判断一颗树是否是镜像对称的。
解法1：使用DFS
public boolean isSymmetric(TreeNode root) { if(root == null) return true; return isSymmetric(root.left, root.right); } public boolean isSymmetric(TreeNode left, TreeNode right) { if(left == null && right == null) return true; else if(left == null || right == null || left.val != right.val) return false; else return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left); }
解法2：使用BFS
public boolean isSymmetric(TreeNode root) { if(root == null) return true; List<TreeNode> list = new ArrayList<TreeNode>(); list.add(root); while(!list.isEmpty()) { int r = list.size() - 1; for(int l=0; l<r;) { TreeNode left = list.get(l); TreeNode right = list.get(r); if(left == null && right == null) { list.remove(r); list.remove(l); r = r-2; } else if(left == null || right == null || left.val != right.val) { return false; } else { l++; r--; } } r = list.size(); for(int i=0; i<r; i++) { TreeNode t = list.remove(0); if(t != null) { list.add(t.left); list.add(t.right); } else { list.add(null); list.add(null); } } } return true; }
原文：http://www.cnblogs.com/linxiong/p/4374989.html