剑指Offer刷题笔记（java实现）_26.树的子结构

题目描述：

　　输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）。

 

其实思路很简单：我们的算法就通过比较即可，因为是树的遍历比较所以第一时间想到了递归

先假设母树为A，子树为B

（1）我们先去判断节点的第一个点的值是否相同，如果相同则进一步遍历以这个节点相同的左右子树是否和B的起点的左右子树的值都相同

（2）如果比较的当前头结点的值都不同我们就要去A树的左右子树找和B树相同的值，如果相同则去遍历到相应的值遍历到后再跳到步骤（1）：

package treeAhavaTreeB_26;

import sun.reflect.generics.tree.Tree;

public class TreeAHasTreeB {
    public static void main(String[] args) {
        int[] arrTreeA = new int[]{0, 1, 2, 3, 4, 5, 6, 7};
        int[] arrTreeB=new int[]{0};
        printTreeDFS(buildTree(arrTreeA, 1));
        printTreeDFS(buildTree(arrTreeB, 1));
      System.out.println(isContain(buildTree(arrTreeA,1),buildTree(arrTreeB,1)));
    }


    /*
     * 建二叉树：按照相应的坐标顺序重建
     * */
    public static TreeRoot buildTree(int[] arr, int index) {
        if (index <= arr.length - 1) {
            TreeRoot treeRoot = new TreeRoot();
            treeRoot.value = arr[index];

            treeRoot.leftRoot = buildTree(arr, index * 2);

            treeRoot.rightRoot = buildTree(arr, index * 2 + 1);
            return treeRoot;
        }
        return null;
    }


    /*
     *   前序遍历
     *   递归遍历
     * */
    public static void printTreeDFS(TreeRoot treeRoot) {
        if (treeRoot != null) {
            System.out.println(treeRoot.value);
            printTreeDFS(treeRoot.leftRoot);
            printTreeDFS(treeRoot.rightRoot);
        }
    }


    //核心算法：是否包含相应的子树
    public static boolean isContain(TreeRoot treeRootA, TreeRoot treeRootB) {
        boolean result = false;
        if (treeRootA != null && treeRootB != null) {
            //（1）.判断每个结点是否相同
               if (treeRootA.value==treeRootB.value){
                  result= everyPointSame(treeRootA,treeRootB);
               }
            //(2).不同则去遍历别的节点
               if (!result)
                   result=isContain(treeRootA.leftRoot,treeRootB);
               if (!result)
                   result=isContain(treeRootA.rightRoot,treeRootB);
        }
        return result;
    }

    private static boolean everyPointSame(TreeRoot treeRootA, TreeRoot treeRootB) {
        //前两个if语句一定要这样的顺序，因为先判断b是否空，为空不管a是否为空都相当于包含了,所以返回true
        //如果判断到第二个语句，说明b不为空，若a为空，说明不包含，结束，所以返回false
        if (treeRootB==null){
             return true;
         }
         if (treeRootA==null){
             return false;
         }
         if (treeRootA.value!=treeRootB.value){
             return false;
         }
        //递归核心算法
       return everyPointSame(treeRootA.leftRoot,treeRootB.leftRoot)&& everyPointSame(treeRootA.rightRoot,treeRootB.rightRoot);
    }
}


class TreeRoot {
    int value;
    TreeRoot leftRoot;
    TreeRoot rightRoot;
}