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.
confused what
"{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ.
/**
* 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;
}
HashMap<Integer, TreeNode> lst = new HashMap<Integer, TreeNode>();
lst.put(0, root);
int length = 1;
while(lst.size()!=0) {
HashMap<Integer, TreeNode> tmp = new HashMap<Integer, TreeNode>();
for(Integer key : lst.keySet()) {
TreeNode node = lst.get(key);
if(node.left!=null) {
tmp.put(key.intValue()*2, node.left);
}
if(node.right!=null) {
tmp.put(key.intValue()*2+1, node.right);
}
}
length *= 2;
for(Integer key : tmp.keySet()) {
TreeNode t1 = tmp.get(key);
TreeNode t2 = tmp.get(length-1-key.intValue());
if((t2==null) || t1.val!=t2.val) {
return false;
}
}
lst = tmp;
}
return true;
}
}
=======
/**
* Definition for a binary tree node.
* 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;
}
return helper(root.left, root.right);
}
private boolean helper(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null || left.val != right.val) {
return false;
}
return helper(left.left, right.right) && helper(left.right, right.left);
}
}
=======
/**
* Definition for a binary tree node.
* 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;
}
return helper(root.left, root.right);
}
private boolean helper(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null || left.val != right.val) {
return false;
}
return helper(left.left, right.right) && helper(left.right, right.left);
}
}
没有评论:
发表评论