剑指offer面试题系列

题目：输入两棵二叉树A和B，判断B是不是A的子结构。

分析

在用数组构造二叉树这一环节上花费了不少功夫。知道了a[i]结点的左孩子就是a[2i + 1],右孩子就是a[2i+2],但是无法让数组元素有这个表示孩子的属性，如果用一个循环来做，但是怎么像用C语言那样，依靠指针的移动来操作二叉树的结点呢？

想不出办法，只好去网上找办法。

于是，有了本例子中的一个方法，使用一个集合存储作为二叉树结点的元素，这样每当取出一个元素的时候，就可以设置它的相关属性了，包括设置其左右孩子的属性。

下面是一段二叉树的创建和打印代码：

public static treeNode BuildTree(int[] arr) {
        ArrayList<treeNode> nodelist = new ArrayList<treeNode>();

        // 将数组转化成二叉树结点
        for (int i = 0; i < arr.length; i++) {
            nodelist.add(new treeNode(arr[i]));
        }

        treeNode root = nodelist.get(0); //设置根节点
        for (int j = 0; j < arr.length / 2; j++) {
            nodelist.get(j).left = nodelist.get(2 * j + 1);
            nodelist.get(j).right = nodelist.get(2 * j + 2);
        }
        return root;
    }

    public static void PreOrder(treeNode root) {
        if (root != null) {
            System.out.println(root.data);
            PreOrder(root.left);
            PreOrder(root.right);
        }
    }

有了创建二叉树的方法，接下来做的就是如何进行比较了。

首先找到在母树中找到子树的根节点，最初的设想是：如果找不到就返回false，如果找到就返回此根节点的指针，然后在另一个函数中进行比较,可是按照这种设想在比较的时候出了问题，也想到肯定用递归比较简单，但是在如何终止递归的时候，不知道该怎么办。

之后想到声明一个boolean型变量flag来返回是true还是false，如果是false的话就不必要再进行右子树的比较了，同时也不必在找到根节点之后返回此指针然后再次调用一个函数来处理，只需要在找到根节点的那一刻继续调用函数处理即可，这里体现出了一定的编程技巧。

代码

public static boolean TreeJudge(treeNode root, treeNode subroot) {
        boolean flag = false;
        if (root == null || subroot == null)
            return flag;

        if (root.data == subroot.data) {
            flag = isSubTree(root, subroot);
        }

        //下面两个if的判断非常巧妙，需要好好领悟

        if (!flag)
            flag = TreeJudge(root.left, subroot);

        if (!flag)
            flag = TreeJudge(root.right, subroot);

        return flag;
    }

    // 判断是否是子树
    public static boolean isSubTree(treeNode root, treeNode subroot) {
        if ((root != null && subroot == null) || root == null
                && subroot != null)
            return false;
        if (root == null && subroot == null)
            return true;
        boolean flag = false;
        if (root.data == subroot.data) {
            flag = isSubTree(root.left, subroot.left);
            if (flag)
                flag = isSubTree(root.right, subroot.right);
        } else {
            flag = false;
        }
        return flag;
    }

总结

编程技巧掌握得不够，还需要大量的练习。