Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
用递归的方法很好做。先比较对应的两个节点数值是否相同，如果相同就看第一个节点的左子和第二个节点的右子是否对称，以及第一个节点的右子和第二个节点的左子。
1 public static boolean isSymmetric(TreeNode root) { 2 if (root == null) return true; 3 else return check(root.left, root.right); 4 } 5 6 public static boolean check(TreeNode left, TreeNode right) { 7 if (left == null && right == null) return true; 8 else if (left != null && right != null) { 9 if (left.val == right.val) { 10 return check(left.left, right.right) && check(left.right, right.left); 11 } 12 else return false; 13 } 14 else return false; 15 }
如果用iterative的方法，还真是一时没想到。一想也不能是dfs，估计就是bfs。但是用bfs怎么能比较同一层的元素是否对称。。。因为我想的是bfs都放到一个list中，要比较是否对称需要把元素都倒出来。然后还要把下一层的放进去。。。就不知道咋做了。。。。
后来网上学习了一下。可以用两个queue。一个queue bfs左子树，一个queue bfs右子树。bfs的顺序不同，一个先左后右，一个先右后左。这样对比每个出队的元素，也不用记录哪层是哪层之类的。。
1 class Solution { 2 public: 3 bool isSymmetric(TreeNode *root) { 4 // Start typing your C/C++ solution below 5 // DO NOT write int main() function 6 if(root==NULL) return true; 7 queue<TreeNode*> q1; 8 queue<TreeNode*> q2; 9 10 q1.push(root->left); 11 q2.push(root->right); 12 13 while(!q1.empty()&&!q2.empty()) 14 { 15 TreeNode *t1=q1.front(); 16 TreeNode *t2=q2.front(); 17 q1.pop(); 18 q2.pop(); 19 20 if((t1!=NULL&&t2==NULL)||(t1==NULL&&t2!=NULL)) 21 return false; 22 23 if(t1!=NULL&&t2!=NULL) 24 { 25 if(t1->val!=t2->val) 26 return false; 27 28 q1.push(t1->left); 29 q1.push(t1->right); 30 q2.push(t2->right); 31 q2.push(t2->left); 32 } 33 } 34 return true; 35 36 } 37 };