LC 572.另一棵树的子树

2024-04-11 00:28
文章标签 子树 一棵树 572 lc

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

572. 另一棵树的子树

给你两棵二叉树 rootsubRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1:

输入: root = [3,4,5,1,2], subRoot = [4,1,2]
输出: true

示例 2:

输入: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出: false

提示:

  • root 树上的节点数量范围是 [1, 2000]
  • subRoot 树上的节点数量范围是 [1, 1000]
  • − 1 0 4 ≤ r o o t . v a l ≤ 1 0 4 -10^4 \leq root.val \leq 10^4 104root.val104
  • − 1 0 4 ≤ s u b R o o t . v a l ≤ 1 0 4 -10^4 \leq subRoot.val \leq 10^4 104subRoot.val104

解法一(迭代+暴力匹配)

思路分析:

  1. 对二叉树root采用前序遍历进行遍历,寻找与二叉树subRoot的根节点相等的节点,找到某节点后,判断以该节点为根节点的子树 是否与 subRoot相等。

实现代码如下:

class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {// 使用统一迭代进行二叉树遍历Deque<TreeNode> stack = new LinkedList<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();if (node.val == subRoot.val) {    // 若出现与subRoot的根节点值相等 则进一步判断是否为子树if (isSameTree(node, subRoot))return true;    // 为子树 则直接返回true}if (node.right != null) stack.push(node.right);if (node.left != null) stack.push(node.left);}return false;}// 判断两棵树是否相等private boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) return true;if (p == null || q == null) return false;return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}
}

提交结果如下:

解答成功:
执行耗时:5 ms,击败了14.15% 的Java用户
内存消耗:43.1 MB,击败了8.66% 的Java用户

复杂度分析:

  • 时间复杂度: O ( m ⋅ n ) O(m \cdot n) O(mn),subRoot是子树,且刚好遍历整个root
  • 空间复杂度: O ( m + n ) O(m+n) O(m+n),递归调用和前序遍历root

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



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

相关文章

【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

从实验室到应用:LC-MS/MS技术与AbMole化合物共舞,揭开半胱氨酸靶向共价抑制剂的新篇章

在生物化学的广阔舞台上,共价抑制剂作为一类特殊的分子“捕手”,它们通过形成稳定的共价键精准捕获目标蛋白的半胱氨酸残基,从而调节其功能。近期,一项由澳门科技大学、暨南大学和中国科学院神经科学研究所携手完成的研究,利用先进的LC-MS/MS技术,结合AbMole BioScience Inc提供的高品质化合物,成功筛选出多种潜在的半胱氨酸靶向共价抑制剂,为科学界带来了一场激动人心的发现之旅。 共价抑

算法---------寻找重复的子树(Java版本)

题目描述: 给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。两棵树重复是指它们具有相同的结构以及相同的结点值。示例 1:1/ \2 3/ / \4 2 4/4下面是两个重复的子树:2/4和4因此,你需要以列表的形式返回上述重复子树的根结点。 解决方法: /*** Definition for a binary tree n

2166. 子树的大小及深度

代码 #include<bits/stdc++.h>using namespace std;vector<int> a[110];int d[110],s[110];int dfs(int x,int y){int i;s[x]=1;d[x]=d[y]+1;for(i=0;i<a[x].size();i++)if(a[x][i]!=y)s[x]=s[x]+dfs(a[x][i

数据结构-非线性结构-树形结构:有序树 ->二叉树 -> 平衡二叉树(任何节点的左右子树的高度差不大于1)-> 完全二叉树(除最底层外的其他层都被填满,且最底层左到右填入) -> 堆(优先队列)

完全二叉树:即除了最底层,其他层的节点都被元素填满,且最底层左到右填入。 完全二叉树属于平衡二叉树。 堆是一种完全二叉树,且满足以下条件: 最大堆:每个节点都比其子树所有节点大的完全二叉树;最小堆:每个节点都比其子树所有节点小的完全二叉树; 我们对堆中的结点按层进行编号,可以将堆逻辑结构映射到数组中 大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i

LC开源电路的学习(一)

TI的升压芯片,电压虽然能升高,但是带来的问题就是最大电流大幅降低: CC1和CC2芯片接快充芯片之后,直接接到单片机的下载口: 这个有点意思,用导线换电阻: 、 PD快充芯片CH224K需要连接typeC的DP DN引脚,但是我想用这两个引脚接ch340给单片机下载程序怎么弄:

HDU 1325(并查集判断一个图是否是一棵树)

题意:每组数据都以0 0结束,-1 -1结束程序。 每组数据中的每两个数字为一小组,前一个数字代表的结点指向后一个数字代表的结点。   #include <iostream>#include <cstring>using namespace std;int father[100010];int find_father(int x){while (father[x] != x)x

leetcode刷题(98)——652. 寻找重复的子树

给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。 两棵树重复是指它们具有相同的结构以及相同的结点值。 示例 1: 1/ \2 3/ / \4 2 4/4 下面是两个重复的子树: 2/4 和 4 因此,你需要以列表的形式返回上述重复子树的根结点。 /*** Definition for a binar

【LC刷题】DAY15:654 617 700 98

【LC刷题】DAY15:654 617 700 98 文章目录 【LC刷题】DAY15:654 617 700 98654. 最大二叉树 [link](https://leetcode.cn/problems/maximum-binary-tree/description/)617. 合并二叉树 [link](https://leetcode.cn/problems/merge-two-b