从零学算法(非官方题库)

news/2024/7/20 21:27:07 标签: 算法, 深度优先

输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构, 即 A中有出现和B相同的结构和节点值。
例如:

给定的树 A:
     3
    / \
   4   5
  / \
 1   2
给定的树 B:
  4 
 /
1

返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1:
输入:A = [1,2,3], B = [3,1]
输出:false
示例 2:
输入:A = [3,4,5,1,2], B = [4,1]
输出:true

  • 首先这里不确定的就是,如果结果为 true,那么 A 中哪个节点为 B 的头结点。既然不确定,那么就遍历树 A,然后判断每个节点是否就是 B 的头结点,或者说以 A 此时节点为头结点是否包含 B。
  • 判断 B 是否为给定头节点的树的子树,那么只需要递归判断每个节点即可。当 B 结点为 null 说明比较完了都没啥问题,那自然返回 true,而如果 A 都被比较完了 B 还有剩下的节点还没判断,那肯定返回 false,或者 A B 此时的结点的值不同,那也返回 false,否则继续比较左右节点。
  •   // 递归遍历树 A
      public boolean isSubStructure(TreeNode A, TreeNode B) {
          return (A!=null && B!=null) && (
              dfs(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B)
          );
      }
      public boolean dfs(TreeNode A,TreeNode B){
          if(B == null)return true;
          if(A == null || A.val != B.val)return false;
          return dfs(A.left,B.left) && dfs(A.right,B.right);
      }
    

http://www.niftyadmin.cn/n/4936938.html

相关文章

nlohmann json:通过[ ]运算符读取设置object/array

除了可以通过at,还可以通过[ ]运算符来读取和设置object/array #include <iostream> #include <nlohmann/json.hpp> using namespace std; using json = nlohmann::json;int main() {json data = R"({"name": "xiaoming","age&quo…

Azure创建第一个虚拟机

首先&#xff0c;登录到 Azure 门户 (https://portal.azure.com/)。在 Azure 门户右上角&#xff0c;点击“虚拟机”按钮&#xff0c;并点击创建&#xff0c;创建Azure虚拟机。 在虚拟机创建页面中&#xff0c;选择所需的基本配置&#xff0c;包括虚拟机名称、操作系统类型和版…

make -C

make -C $MAXIEYE_BUILD_DIR p$1 clean -j$JOBS_NPROC-C 大写&#xff0c;切换到指定目录再执行 make 过程&#xff0c;makefile 在这个指定目录里面

自主学习库简化智能代理创建

观看当今毁灭人类的智能代理玩复杂的视频游戏可能很有趣 - 但创建一个是另一回事。构建有效的智能代理需要设置大量超参数来塑造环境、建立奖励等。来自马萨诸塞大学阿默斯特分校的一组研究人员试图通过他们新的自主学习图书馆项目来简化这一过程。 自治学习库是 PyTorch 的深…

Go Web--Go Module

目录 一、Go Module 1、开启Go Module 2、Go Module基本操作 3、使用GoLand创建Go Module项目 4、GoLand配置File Watchers 一、Go Module Go Module包管理工具----相当于Maven 1.11版本引入 1.12版本正式支持 告别GOPATH&#xff0c;使用Go Module管理项目&#xff0c…

Netty:获取ByteBuf的切片

说明 io.netty.buffer.ByteBuf有几个获取切片的函数。 retainedSlice(int index, int length)&#xff1a;获取本buffer从位置index开始&#xff0c;长度为length个字节的一个切片&#xff0c;本buffer和返回的切片buffer的引用计数增加1。修改本buffer和切片buffer的内容互相…

Ubuntu下mysql安装及远程连接支持配置

1.安装 下载mysql-server&#xff08;必须加sudo&#xff09; sudo apt update sudo apt install mysql-server 查看mysql的状态 sudo service mysql status 通过如下命令开启mysql sudo service mysql start 2.配置 第一次安装mysql后&#xff0c;为root设置一个密码 …

Java类与对象详解(3)

目录 封装 封装的概念 访问限定符 封装扩展之包 包的概念 导入包中的类 自定义包 基本规则 包的访问权限控制举例 常见的包 static 成员 static 修饰成员变量 static修饰成员方法 static 成员变量的初始化 代码块 代码块的概念及其分类 普通代码块 构造代码块…