[LeetCode 101]Symmetric Tree

题目链接：symmetric-tree

import java.util.LinkedList;//判断该二叉树是否是对称二叉树/** * 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 3But the following is not:1/ \2 2\ \3 3Note:Bonus points if you could solve it both recursively and iteratively. * */public class SymmetricTree {public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}}//解法一：递归版//192 / 192 test cases passed.//Status: Accepted//Runtime: 248 ms//Submitted: 0 minutes agopublic boolean isSymmetric(TreeNode root) {if(root == null) return true;return isSymmetric(root.left, root.right);}public boolean isSymmetric(TreeNode p, TreeNode q) {if(p == null && q == null) return true;if(p == null || q == null) return false;return p.val == q.val&& isSymmetric(p.left, q.right)&& isSymmetric(p.right, q.left);}//解法二：遍历版//192 / 192 test cases passed.//Status: Accepted//Runtime: 240 ms//Submitted: 0 minutes agopublic boolean isSymmetric1(TreeNode root) {if(root == null) return true;LinkedList<TreeNode> queue = new LinkedList<TreeNode>();queue.add(root);while(!queue.isEmpty()) {int levelLen = queue.size();//判断 每层是否对称int p = 0;int q = levelLen – 1;while(p < q) {TreeNode nodeP = queue.get(p);TreeNode nodeQ = queue.get(q);if(nodeP == null && nodeQ != null ) return false;else if(nodeP != null && nodeQ == null ) return false;else if( nodeP != null && nodeQ != null && nodeP.val != nodeQ.val) return false;//else if( nodeP == null && nodeQ == null) 不处理;p ++;q –;}//子节点入队for (int i = 0; i < levelLen; i++) {TreeNode node = queue.removeFirst();if(node != null ) {queue.add(node.left);queue.add(node.right);}}}return true;}public static void main(String[] args) {// TODO Auto-generated method stub}}

，天下没有不散的宴席，也许这人间真的只有朦朦胧胧才是真。