剑指OFFER：26：树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

限制：

0 <= 节点个数 <= 10000

Related Topics

树

深度优先搜索

二叉树

深度优先遍历

• 递归遍历A树的每一个节点是否和B的根节点相等
  • 如果相等，则进行比较是否是子结构，抽象出一个方法进行比较。

class Solution {
    //递归遍历A的每一个节点是否等于B，相等则判断是否为子节点
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        boolean result = false;
        //当 A、B不等于NULL时，判断B是否为A的子结构
        if(A != null && B != null){
            //相等则进行判断
            if(A.val == B.val){
                result = isEquals(A,B);
            }
            //如果不是 继续递归左子树
            if(!result){
                result = isSubStructure(A.left,B);
            }
            //如果不是 继续递归右子树
            if(!result){
                result = isSubStructure(A.right,B);
            }
        }
        //返回结果
        return result;
    }
    //判断node2是不是node1的子结构
    public  boolean isEquals(TreeNode node1,TreeNode node2){
        //当子结构是null
        if(node2 == null){
            return true;
        }
        //node1为空，node2不为空，无法匹配
        if(node1 == null){
            return false;
        }
        //node1和node2的值不相等、无法匹配
        if(node1.val != node2.val){
            return false;
        }
        //如果当前节点匹配，判断B的左子树和右子树
        return isEquals(node1.left,node2.left) && isEquals(node1.right,node2.right);
    }
}