判断一棵树是否是另一棵树的子树 java实现

时间:2022-08-26 20:49:19

        这是一个很经典的算法题,听起来好像挺难的,但是其实很简单。我觉得我们接触到的问题,并没有难题,只有复杂不复杂。一个再难的问题,也可以分解成一个个简单的问题,再将这些简单的问题交给不同的人去做就构成了一个项目。其实写算法也是这个思想。

         首先要判断一棵树是不是另一棵树的子树,我们只需遍历一棵树,用这个树的每一个节点去和另一棵树比较。那么这个问题就被

转化成了,如何遍历一棵树和如何判断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。