参考 http://www.cnblogs.com/feiling/p/3251061.html & http://fisherlei.blogspot.com/2013/01/leetcode-symmetric-tree.html
非递归解法：按层遍历，每一层检查一下是否对称。
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isSymmetric(TreeNode root) { if(root == null) { return true; } LinkedList<TreeNode> l = new LinkedList<TreeNode>(), LinkedList<TreeNode> r = new LinkedList<TreeNode>(); l.add(root.left); r.add(root.right); while(!l.isEmpty() && !r.isEmpty()) { TreeNode t1 = l.poll(); TreeNode t2 = r.poll(); if((t1 == null && t2 != null)||(t2 == null && t1 != null)){ return false; } if( t1 != null){ if(t1.val != t2.val){ return false; } l.add(t1.left); l.add(t1.right); r.add(t2.right); r.add(t2.left); } } return true; } }
递归解法：
其中左子树和右子树对称的条件：
- 两个节点值相等，或者都为空
- 左节点的左子树和右节点的右子树对称
- 左节点的右子树和右节点的左子树对称
-
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isSymmetric(TreeNode root) { if(root == null) { return true; }else{ return symCheck(root.left, root.right); } } public boolean symCheck(TreeNode leftN, TreeNode rightN){ if(leftN == null) return rightN == null; if(rightN == null) return leftN == null; if(leftN.val != rightN.val){ return false; } if(!symCheck(leftN.left, rightN.right)){ return false; } if(!symCheck(leftN.right, rightN.left)){ return false; } return true; } }