题目：
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.
思路：
1) 递归
package tree; public class SymmetricTree { public boolean isSymmetric(TreeNode root) { if (root == null) return true; return isSymmetric(root.left, root.right); } private boolean isSymmetric(TreeNode left, TreeNode right) { if (left == null && right == null) return true; if (left == null || right == null) return false; return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left); } }
2) 迭代
package tree; import java.util.Stack; public class SymmetricTree { public boolean isSymmetric(TreeNode root) { if (root == null) return true; Stack<TreeNode> stack1 = new Stack<TreeNode>(); Stack<TreeNode> stack2 = new Stack<TreeNode>(); TreeNode p = root.left; TreeNode q = root.right; while ((p != null && q != null) || (!stack1.isEmpty() && !stack2.isEmpty())) { while (p != null && q != null) { stack1.push(p); p = p.left; stack2.push(q); q = q.right; } if (p != null || q != null) return false; if (stack1.isEmpty() && stack1.isEmpty()) return true; if (stack1.isEmpty() || stack1.isEmpty()) return false; TreeNode node1 = stack1.pop(); TreeNode node2 = stack2.pop(); if (node1.val != node2.val) return false; p = node1.right; q = node2.left; } return p == null && q == null && stack1.isEmpty() && stack2.isEmpty(); } }