面试算法：镜像二叉树的检测
更详细的讲解和代码调试演示过程，请参看视频
如何进入google,算法面试技能全面提升指南
如果你对机器学习感兴趣，请参看一下链接：
机器学习：神经网络导论
有一种特殊的二叉树具备镜像特性，如果你从二叉树的中间切一刀，然后把左边反转到右边，你会发现左右是能够重合的。例如下面的二叉树就具备镜像二叉树的特性：
这里写图片描述
而下面的二叉树就不具备镜像特性：
算法要求是，给定一颗二叉树的根节点，判断该二叉树是否具备镜像特性。
大家是否还记得，以前我们讲过如何层次遍历一颗二叉树。遍历时，现将根节点加入队列，然后把根节点的左孩子和右孩子分别加入队列，接着把队列里第二个元素的左右孩子依次加入队列，最终我们得到一个由二叉树节点构成的队列。
要判断一颗二叉树是否具备镜像属性，在层次遍历节点的时候，我们做一次变换，第一次遍历节点时，每次都是把当前节点的左孩子和右孩子依次加入队列末尾。第二次遍历时，节点加入队列的次序做一次调换，先把右孩子加入队列，再把左孩子加入队列，如果两次所形成的队列是一样的话，那么该二叉树就具备镜像属性，举个例子，例如下面二叉树：
这里写图片描述
层次遍历上方二叉树时，如果是按照父节点，左子节点，右子节点的次序加入队列的话，那么最终队列如下：
5->6->6->1->2->1->2->4->3->6->7->8->7->3->4
如果是按照父节点，右子节点，左子节点的次序加入队列的话，得到的最终队列也是：
5->6->6->1->2->1->2->4->3->6->7->8->7->3->4
这两个队列是一样的，所以可以断定二叉树具备镜像属性。以下是算法实现：
import java.util.ArrayList;
public class SymmetricTree {
private ArrayList<TreeNode> treeList1 = new ArrayList<TreeNode>();
private ArrayList<TreeNode> treeList2 = new ArrayList<TreeNode>();
private boolean isSymmetric = false;
private void treeToList(TreeNode root, ArrayList<TreeNode> list, boolean isLeft) {
list.add(root);
int pos = 0;
while (pos < list.size()) {
TreeNode n = list.get(pos);
if (n != null) {
TreeNode n1;
TreeNode n2;
if (isLeft) {
n1 = n.left;
n2 = n.right;
} else {
n1 = n.right;
n2 = n.left;
}
list.add(n1);
list.add(n2);
}
pos++;
}
}
public SymmetricTree(TreeNode root) {
treeToList(root, treeList1, false);
//mirrorTree(root);
treeToList(root, treeList2, true);
isSymmetric = compareList(treeList1, treeList2);
}
public boolean isSymmetric() {
return isSymmetric;
}
private boolean compareList(ArrayList<TreeNode>l1, ArrayList<TreeNode> l2) {
if (l1.size() != l2.size()) {
return false;
}
int pos = 0;
while (pos < l1.size()) {
TreeNode n1 = l1.get(pos);
TreeNode n2 = l2.get(pos);
if (n1 == null && n2 != null) {
return false;
}
if (n1 != null && n2 == null) {
return false;
}
if (n1 == null && n2 == null) {
pos++;
continue;
}
if (n1.vaule != n2.vaule) {
return false;
}
pos++;
}
return true;
}
}
SymmetricTree 用来判断给定二叉树是否具备镜像属性。它的treeToList接口用来层次遍历二叉树并形成队列，如果isLeft参数的值是true, 那么层次遍历二叉树时，使用的次序是父节点，左子节点，右子节点。如果isLeft的参数值是false,那么层次遍历时，使用的次序就是父节点，右子节点，左子节点。
compareList 用于比较两个队列，节点的值是否一样，进而得到两个队列是否是等价的。在TreeUtil类中，我们构造一颗本文开头所描述的二叉树：
public class TreeUtil {
private TreeNode root = null;
public void addTreeNode(TreeNode node) {
if (root == null) {
root = node;
return;
}
TreeNode cur = root, prev = root;
while (cur != null) {
prev = cur;
if (cur.vaule > node.vaule) {
cur = cur.left;
} else {
cur = cur.right;
}
}
if (prev.vaule > node.vaule) {
prev.left = node;
} else {
prev.right = node;
}
}
public TreeNode getTreeRoot() {
return root;
}
public TreeNode getSymmetricTree() {
TreeNode n = new TreeNode(314);
n.left = new TreeNode(6);
n.left.right = new TreeNode(2);
n.left.right.right = new TreeNode(3);
n.right = new TreeNode(6);
n.right.left = new TreeNode(2);
n.right.left.left = new TreeNode(3);
return n;
}
}
入口函数的代码如下：
public class BinaryTree {
public static void main(String[] s) {
TreeUtil util = new TreeUtil();
TreeNode r = util.getSymmetricTree();
SymmetricTree sym = new SymmetricTree(r);
boolean t = sym.isSymmetric();
System.out.println("is the tree symmetric? : " + t);
}
}
上面代码首先构造一颗二叉树，然后把二叉树节点传给SymmetricTree类，如果传入的二叉树具备镜像属性，那么 isSymmetric调用会返回true, 要不然会返回false。
由于二叉树的层次遍历，需要对每个节点都访问一次，因此算法的时间复杂度是O(n), 算法运行中没有分配新的内存，因此算法的空间复杂度是O(1)。更详细的讲解和代码演示，请参看视频。
更多技术信息，包括操作系统，编译器，面试算法，机器学习，人工智能，请关照我的公众号：
