聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

面试官:你听说过树的子结构吗?

2021-12-03 02:12 浏览: 2856853 次 我要评论(0 条) 字号:

来自公众号:五分钟学算法


大家好,我是吴师兄,不啰嗦,直接开始今天的算法学习,冲冲冲。

一、题目描述

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

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

二、保姆级参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 一开始如果 A 或者 B 为空,直接返回 false
        // 因为题目约定空树不是任意一个树的子结构
        if( A == null || B == null){
            return false;
        }
        // 接下来去以下几种情况
        // A 的根节点 VS B 的根节点( A 的左右子树的节点 VS B 的根节点)
        // 1、A 的根节点和 B 的根节点相同情况,依次比较它们的子节点
        // 2、A 的根节点和 B 的根节点不相同情况, A 的左子树 VS B 的根节点
        // 3、A 的根节点和 B 的根节点不相同情况, A 的右子树 VS B 的根节点
        return isSub(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }

    boolean isSub(TreeNode A, TreeNode B){

        // A 和 B 不匹配的情况有很多,我们需要一开始去找它们完全匹配的情况
        // 即遍历完 B ,直到为 null,说明 B 的全部节点都和 A 的子结构匹配上
        if( B == null ){
            return true;
        }

        // A 中的节点为空,但 B 中的节点不为空,说明不匹配
        if( A == null ){
            return false;
        }

        // A 和 B 都不为空 ,但数值不同,说明不匹配
        if(  A.val != B.val){
            return false;
        }

        // 此时,当前这个点是匹配的,继续递归判断左子树和右子树是否「分别匹配」
        return isSub(A.left, B.left) && isSub(A.right, B.right);

    }
}

三、视频讲解



--- EOF ---


推荐↓↓↓


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复