Symmetric Tree（中心对称树）

Symmetric Tree（中心对称树）

题目原型：

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

基本思路：

根据例子我们发现，每一层，给定两个指针分别从左端和右端开始，只有当左端的左子树的值等于右端的右子树的值，并且左端的右子树的值等于右端左子树的值时，此树便称为中心对称树（Symmetric Tree）。

	public boolean isSymmetric(TreeNode root){if(root==null)return true;ArrayList<TreeNode> list = new ArrayList<TreeNode>();list.add(root);boolean isFirst = true;while(list.size()>0){if(list.size()%2==1&&isFirst==false)return false;for(int i = 0,j=list.size()-1;i<=j;i++,j--){TreeNode one = list.get(i);TreeNode two = list.get(j);if(one.left!=null&&two.right!=null){if(one.left.val!=two.right.val)return false;}if(one.right!=null&&two.left!=null){if(one.right.val!=two.left.val)return false;}if((one.left==null&&two.right!=null)||(one.left!=null&&two.right==null))return false;}//加入下一层节点int size = list.size();while(size>0){if(list.get(0).left!=null)list.add(list.get(0).left);if(list.get(0).right!=null)list.add(list.get(0).right);list.remove(0);size--;}isFirst = false;//表示不是第一层了}return true;}

Symmetric Tree（中心对称树）

题目原型：

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

基本思路：

根据例子我们发现，每一层，给定两个指针分别从左端和右端开始，只有当左端的左子树的值等于右端的右子树的值，并且左端的右子树的值等于右端左子树的值时，此树便称为中心对称树（Symmetric Tree）。

	public boolean isSymmetric(TreeNode root){if(root==null)return true;ArrayList<TreeNode> list = new ArrayList<TreeNode>();list.add(root);boolean isFirst = true;while(list.size()>0){if(list.size()%2==1&&isFirst==false)return false;for(int i = 0,j=list.size()-1;i<=j;i++,j--){TreeNode one = list.get(i);TreeNode two = list.get(j);if(one.left!=null&&two.right!=null){if(one.left.val!=two.right.val)return false;}if(one.right!=null&&two.left!=null){if(one.right.val!=two.left.val)return false;}if((one.left==null&&two.right!=null)||(one.left!=null&&two.right==null))return false;}//加入下一层节点int size = list.size();while(size>0){if(list.get(0).left!=null)list.add(list.get(0).left);if(list.get(0).right!=null)list.add(list.get(0).right);list.remove(0);size--;}isFirst = false;//表示不是第一层了}return true;}