对称二叉树
请实现一个函数,用来判断一棵二叉树是不是对称的
如果一棵二叉树和它的镜像一样,那么它是对称的
分析:
根据前序遍历,先遍历根结点,再遍历左结点,后遍历右结点,设计出一种镜像遍历方式:先遍历根结点,再遍历右结点,后遍历左结点,得到两个序列对应该完全相同
public class SymmetricalBinaryTree<Key extends Comparable<Key>> {
private class Node {
public Key key;
public Node left, right;
public Node(Key key) {
this.key = key;
}
}
public boolean isSymmetrical(Node node) {
return isSymmetrical(node, node);
}
private boolean isSymmetrical(Node m, Node n) {
if (m == null && n == null) {
return true;
}
if (m == null || n == null) {
return false;
}
if (m.key.compareTo(n.key) != 0) {
return false;
}
return isSymmetrical(m.left, n.right) && isSymmetrical(m.right, n.left);
}
}
网友评论