这是一个很经典的算法题,听起来好像挺难的,但是其实很简单。我觉得我们接触到的问题,并没有难题,只有复杂不复杂。一个再难的问题,也可以分解成一个个简单的问题,再将这些简单的问题交给不同的人去做就构成了一个项目。其实写算法也是这个思想。
首先要判断一棵树是不是另一棵树的子树,我们只需遍历一棵树,用这个树的每一个节点去和另一棵树比较。那么这个问题就被
转化成了,如何遍历一棵树和如何判断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。