题目：

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

二叉树的定义类

public BinaryTreeNode{
    int mValue;
    BinaryTreeNode mLeft;
    BinaryTreeNode mRight;
}

思路分析：

• 判断B是不是A的子树，这个问题，分为两部
• 首先遍历二叉树找到A树和B的根节点相同的树，不同的继续遍历。
• A树中找到和B树的根节点相同的树，然后递归的判断左右节点是不是也相同。

代码：

class BinaryTreeNode{
        int mValue;
        BinaryTreeNode mLeft;;
        BinaryTreeNode mRight;
    }
    boolean hasSubTree(BinaryTreeNode a,BinaryTreeNode b){
        boolean result = false;
        if(a != null && b != null){
            if(a.mValue == b.mValue){
                result = dosTreeHave(a,b);
            }
            if(!result){
                result = hasSubTree(a.mLeft,b);
            }
            if(!result){
                result = hasSubTree(a.mRight,b);
            }
        }
        return result;
    }
    boolean dosTreeHave(BinaryTreeNode c,BinaryTreeNode d){
        if(d == null){
            return true;
        }
        if(c == null){
            return false;
        }
        return dosTreeHave(c.mLeft,d) && dosTreeHave(c.mRight,d);
    }

测试用例：

• b是和不是a的子树
• a和b分别是null，都是null，二叉树的所有结点都没有左子树或者右子树

参考：

剑指offer

安利一个面试题汇总的微信订阅号。每天推送经典面试题和面试心得技巧，都是干货！

微信订阅号名称：IT面试题汇总

微信订阅号二维码如下：