另一棵树的子树(oj题)

2024-05-31 22:36
文章标签 子树 oj 一棵树

本文主要是介绍另一棵树的子树(oj题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、题目链接

https://leetcode.cn/problems/subtree-of-another-tree/submissions/536304222

二、题目思路

1.首先遍历大树,判断大树的根结点的值是否等于小树的根结点的值,如果不相等,就找大树的左孩子或者右孩子,以左孩子为根的结点的,如果等于小树的根结点的值,就调用判断两棵树是否相等的函数
 

2.如果返回值是true就说明小树是大树的子数,直接return true   。 如果不是,就要继续找该结点的左孩子或者右孩子继续判断,不能return false 。直到大树到了空节点时,说明小树不是大树的子树,return false。

3.左右子树之一符合就说明小树是大树的子树

三、题解代码

//判断两棵树是否相等函数
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//如果两颗树的根结点都是空,说明是相同的结点if(p==NULL&&q==NULL)return true;//如果两棵树的根结点只是其中之一为空,说明不是相同的结点if(p==NULL||q==NULL) return false;//如果两棵树的根结点都存在,但是值不相等,说明也不是相同的结点if(p->val!=q->val)return false;//每个结点的左右孩子结点都要综合判断return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}//遍历大树的所有结点,判断以当前的结点为根结点的树,是否与小树相等
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(root==NULL)//如果大树遍历到空结点,说明小树不是大树的子树return false;//如果当前的根结点和小树的根结点的值相等,就调用判断两颗树是否相等函数if(root->val==subRoot->val)   {if(true==isSameTree(root,subRoot))//如果得到的是true就将结果返回,不是就不要返回return true;                       //因为还要判断以接下来的结点为根的树}// 左右子树其中之一成功就说明小树是大树的子树return isSubtree(root->left,subRoot) ||isSubtree(root->right,subRoot);}

这篇关于另一棵树的子树(oj题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1019232

相关文章

哈理工OJ 2179(深搜)

组合 Time Limit: 1000 MSMemory Limit: 32768 K Total Submit: 7(5 users)Total Accepted: 6(5 users)Rating: Special Judge: No Description 给出一个正整数N,从集合{1,2,3..N} 中找出所有大小为k的子集, 并按照字典序从小到大输出。 Input 第一行是一个整

每日OJ_牛客_求和(递归深搜)

目录 牛客_求和(递归深搜) 解析代码 牛客_求和(递归深搜) 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数,如果累加和大于等于目标,结束递归。此时如果累加和正好等于目标,则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程,找到所有的组合。 #include <iostream>#include <cmath>#in

OJ-0905

题目 示例1: 输入:10 10 56 34 99 1 87 8 99 3 255 6 99 5 255 4 99 7 255 2 99 9 255 213 4输出:99 示例2: 输入:10 10 255 34 0 1 255 8 0 3 255 6 0 5 255 4 0 7 255 2 0 9 255 213 5输出:255 import java.util.

每日OJ_牛客_Emacs计算器(逆波兰表达式)

目录 牛客_Emacs计算器(逆波兰表达式) 解析代码 牛客_Emacs计算器(逆波兰表达式) Emacs计算器__牛客网 解析代码 逆波兰表达式(后缀表达式)求值,需要借助栈,思路: 循环输入,获取逆波兰表达式,然后进行以下补助,直到测试完所有的测试用例: 遇到数字字符串,将该数字字符串转化为数字然后入栈。遇到操作符时,从栈顶取两个数字,然后进行该运算符所对应运算

【HDU】5574 Colorful Tree【子树染色,询问子树颜色数——线段树+bit+lca+set】

题目链接:【HDU】5574 Colorful Tree 题目大意:对一个子树染色,询问一个子树的颜色数。 题目分析: set set维护每种颜色所在的 dfs dfs序区间,修改均摊 nlogn nlogn。 #include <bits/stdc++.h>using namespace std ;typedef long long LL ;typedef pair < int , i

git如何设置嵌套仓库(设置子树或子模块),并解决直接将一个仓库拖拽到另一个仓库中导致的问题

git 将一个仓库拷贝到另一个仓库的文件夹下。默认git并不会处理,上传上去之后,只会创建一个文件夹,但是这个文件夹点不开。 在 git add . 的时候,会报出警告: 警告:正在添加嵌入式 git 仓库:client提示: You've added another git repository inside your current repository.提示: Clones of

西北工业大学oj题-兔子生崽

题目描述: 兔子生崽问题。假设一对小兔的成熟期是一个月,即一个月可长成成兔,每对成兔每个月可以生一对小兔,一对新生的小兔从第二个月起就开始生兔子,试问从一对兔子开始繁殖,一年以后可有多少对兔子? 这道题目一眼看过去就是典型的递归问题,代码如下 public class RabbitReproduction {public static void main(String[] args) {in

★ 算法OJ题 ★ 力扣209 - 长度最小的子数组

Ciallo~(∠・ω< )⌒☆ ~ 今天,简将和大家一起做一道滑动窗口算法题--长度最小的子数组~ 目录 一  题目 二  算法解析 解法⼀:暴力求解 解法二:滑动窗口 三  编写算法 一  题目 209. 长度最小的子数组 - 力扣(LeetCode) 二  算法解析 解法⼀:暴力求解 算法思路: 从前往后枚举数组中的任意⼀个元素,把它当成起始位置

OJ-0903

题目 示例1 输入:30 12 25 8 19输出:15 示例2 输入:10 12 25 8 19 8 6 4 17 19 20 30输出:-1 题解 import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Main {public static

【负载均衡式在线OJ】Compile_server 模块

文章目录 程序源码compile_server整体思路编译(compile.hpp)运行模块编译运行模块编译运行服务 程序源码 https://gitee.com/not-a-stupid-child/online-judge compile_server 整体思路 这个服务要对oj_server 发送过来的代码进行编译和运行,最后把结果返回给oj_server。 所以我