这是一个很经典的算法题，听起来好像挺难的，但是其实很简单。我觉得我们接触到的问题，并没有难题，只有复杂不复杂。一个再难的问题，也可以分解成一个个简单的问题，再将这些简单的问题交给不同的人去做就构成了一个项目。其实写算法也是这个思想。
首先要判断一棵树是不是另一棵树的子树，我们只需遍历一棵树，用这个树的每一个节点去和另一棵树比较。那么这个问题就被
转化成了，如何遍历一棵树和如何判断2棵树是否相等。
我选择用层次遍历的方式来遍历这棵树
public static boolean levelSearch(Node root,Node child){
Deque<Node> deque = new Deque<Node>();
deque.add(root);
while(deque.size()!=0){
Node node = deque.peekFirst();
if(node.isSame(child)==true)
return true;
if(node.left!=null)
deque.add(node.left);
if(node.right!=null)
deque.add(node.right);
}
return false;
}
很明显上面就是一个广度优先遍历算法，那么接下来我们只需要实现isSame()方法了，这个也很简单
public static boolean isSame(Node node1,Node node2){
if((node1==null&&node2!==null)||((node2==null&&node1!==null)))
return false;
if(node1==null&&node2==null){
}
if(node1!=null&&node2!=null){
if(node1.value!=node2.value)
return false;
if(!isSame(node1.left,node2.left))
return false;
if(!isSame(node1,right,node2.right))
return false;
}
}
这里很简单，将所有不同的情况都列举出来，一旦出现就返回false，如果在整个遍历过程中都没有出现false，最后返回true。