Sword to Offer-26 树的子结构 ❀❀

13 Apr 2020 in Algorithm

• 题目描述：
  输入两棵二叉树A，B，判断B是不是A的子结构。
  约定空树不是任意一个树的子结构。

解题思路：

递归调用：
1、HasSubtree方法：
若树root1有一个子树是root2，分为两种情况，树root1就是（is）树root2或者树root1的左右子树中包含（has）树root2，建立递归调用，返回false条件为树root1或者树root2为null（题目规定空树不为任何树的子结构）。
2、isSubTree方法：
若root2为null，表示树root2匹配完毕返回true；
若root2不为null时root1为null，表示匹配失败返回false；
若本次对比的两结点value不相等，表示两树不匹配，返回false；
若root1和root2都不为null，且本次对比的两结点value也相等，进入递归进行子树的对比。

问题图解：

AC代码：

// Whether Tree root2 Is A SubTree of Tree root1

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if (root1==null || root2==null) {
            return false;
        }
        return isSubtree(root1, root2) || HasSubtree(root1.left, root2) 
            || HasSubtree(root1.right, root2);
    }
    
    private boolean isSubtree(TreeNode root1, TreeNode root2) {
        //对比结束，匹配成功
        if (root2 == null) {
            return true;
        }
        //树root2该结点不为null，树root1该结点为null
        if (root1 == null) {
            return false;
        }
        //本次对比的结点值不相等
        if (root1.val != root2.val) {
            return false;
        }
        //本次对比的结点值相等，其左右子树都相同才能匹配成功
        return isSubtree(root1.left, root2.left) && isSubtree(root1.right, root2.right);
    }
}

补充说明：

• 这里是牛客编码链接