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.
Bonus points if you could solve it both recursively and iteratively.
Solution 1: recursive
public class Solution {
public boolean isSymmetric(TreeNode root) {
return dfs(root, root);
}
private boolean dfs(TreeNode x, TreeNode y) {
if (x==null && y==null) return true;
if (x==null || y==null) return false;
if (x.val!=y.val) return false;
return dfs(x.left, y.right) && dfs(x.right, y.left);
}
}
Solution 2: iterative
public class Solution {
public boolean isSymmetric(TreeNode root) {
Deque<TreeNode> s1=new LinkedList<>();
Deque<TreeNode> s2=new LinkedList<>();
TreeNode x=root, y=root;
while (x!=null || y!=null || !s1.isEmpty()) {//s1,s2 always pop.push same time
if (x!=null || y!=null) {
if (x==null || y==null) return false;
if (x.val!=y.val) return false;
s1.push(x);
s2.push(y);
x=x.left;
y=y.right;
}
else {
x=s1.pop();
y=s2.pop();
x=x.right;
y=y.left;
}
}
return true;
}
}
没有评论:
发表评论