树的子结构

方法：递归求解
根据题意可知，需要一个函数判断树A和树B是否有相同的结构。显然是个递归程序。可考察递归程序3部曲。

1. 递归函数的功能：判断2个数是否有相同的结构，如果相同，返回true，否则返回false
2. 递归终止条件：
   如果树B为空，返回true，此时，不管树A是否为空，都为true
   否则，如果树B不为空，但是树A为空，返回false，此时B还没空但A空了，显然false
3. 下一步递归参数：
   如果A的根节点和B的根节点不相等，则只需要用递归函数判断该节点的左子树和右子树是否与树B同结构
   否则，相等，就继续判断A的左子树和B的左子树以及A的右子树和B的右子树是否相同。还需要用递归函数判断该节点的左子树和右子树是否与树B同结构

     public boolean HasSubtree(TreeNode root1,TreeNode root2) {
         if (root1 == null || root2 == null) {
             return false;
         }
         return CheckSubTree(root1, root2);
     }
     private boolean CheckSubTree(TreeNode root1, TreeNode root2) {
         if (root2 == null) {
             return true;
         }
         if (root2 != null && root1 == null) {
             return false;
         }
         if (root1.val == root2.val) {
             return CheckSubTree(root1.left,root2.left)&&CheckSubTree(root1.right,root2.right)
                     ||CheckSubTree(root1.left,root2)||CheckSubTree(root1.right, root2);
         }
         return CheckSubTree(root1.left,root2)||CheckSubTree(root1.right, root2);
     }