剑指Offer：树的子结构【26】
2024-09-08 12:14:10
剑指Offer：树的子结构
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
解题思路
实话实说这道题是剑指Offer前半部分难度比较大的，我们先来思考一个简单情况，如下图，左树枝叶比右树繁茂，但是枝干是相同的，不同的枝叶情况不一样。
此时，我们如何确定说根节点相同的左树包含右树呢？右树有的节点，我左树在对应位置都有！单反有一个节点值或位置不对，则说明左树不包含右树。我们成这个算法为F(X,Y)。
我们再来考虑一种复杂情况，即左树存在多个和右树根节点相同的节点x1、x2....，此时我们以x1、x2....分别作为为根节点和右树进行F(X,Y)即可，只要有一个能够返回TRUE，则认为左树包含右树。
递归代码言简意赅，但是理解起来确实有点难度！？
Java题解
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1==null||root2==null)
return false;
if(root1.val==root2.val&&isContain(root1,root2)){
return true;
}
return HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
}
/**
* 比较是否包含
* @param node1
* @param node2
* @return
*/
public boolean isContain(TreeNode node1, TreeNode node2){
//我为空，你不为空，说明我不包含你
if(node1==null&&node2!=null)
return false;
//咱俩都空，等于值相同
if(node2==null)
return true;
return node1.val == node2.val&& isContain(node1.left, node2.left) && isContain(node1.right, node2.right);
}
}
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
最新文章
- 第九章 springboot + mybatis + 多数据源 （AOP实现）(转载)
- 两排滚动js
- 初学java之接口基础
- ORACLE的分组统计之ROLLUP(一)
- HDU 1881
- 论i++与++i
- eclipse 查看快捷键
- Java基础语法<十一> 异常 断言 日志 调试
- Spring事务的传播行为和隔离级别
- 关于String中的不变模式
- Frame Stacking（拓扑排序）
- SpringMVC格式转化错误之HTTP Status [400] – [Bad Request]
- Failed to fetch URL http://dl-ssl.google.com/android/repository/addons_list-2.xml, reason:
- Node.js Error: Cannot find module express的解决办法
- 559. Maximum Depth of N-ary Tree
- tp框架设置404页面
- WARING
- 20162322 朱娅霖 作业005&006 栈，队列
- react小知识2
- 23种设计模式之原型模式（Prototype）