数据结构和算法-判断一棵二叉树是否为另一颗二叉树的子树
题目:判断下方两棵二叉树右方的二叉树是否为左方二叉树的子树
例1:
| |
/-----------10(10)------\ /-------10(10)------\
| | | |
/-------5(5)\ /-----15(15)\ 5(5)\ /-----15(15)\
| | | | | | |
3(3)\ 7(7)\ 12(12) 18(18) 7(7) 12(12) 18(18)
| |
4(4) 8(8)
通过比较可知,左边的二叉树是右方的子树
例2:
|
/-----------10(10)------\ |
| | /-----15(15)\
/-------5(5)\ /-----15(15)\ | |
| | | | 12(12) 18(18)\
3(3)\ 7(7)\ 12(12) 18(18) |
| | 20(20)
4(4) 8(8)
比较后可知,右方的二叉树不是左方二叉树的子树
编码思路也很简单,就是逐个比较右方的二叉树的每个节点,以及每个分支,是否再左方的二叉树中存在即可。
java测试代码
/**
* 二叉树结点类
* @author 硅谷探秘者(jia)
*/
class Node{
public int data;
public Node left;
public Node right;
public Node(Node left,Node right,int data) {
this.left=left;
this.right=right;
this.data=data;
}
public Node(int data) {
this.data=data;
}
}
public class A1 {
public static void main(String[] args) {
Node root;
Node compare;
/**
* 构造第一颗二叉树
*/
Node n4=new Node(4);
Node n8=new Node(8);
Node n12=new Node(12);
Node n18=new Node(18);
Node n3=new Node(null,n4,3);
Node n7=new Node(null,n8,7);
Node n5=new Node(n3,n7,5);
Node n15=new Node(n12,n18,15);
Node n10=new Node(n5,n15,10);
root=n10;
/**
* 构造第二课二叉树(测试1)
*/
Node c3=new Node(3);
Node c7=new Node(7);
Node c5=new Node(c3,c7,5);
/**
* 构造第二课二叉树(测试2)
*/
Node c_2_8=new Node(8);
Node c_2_7=new Node(null,c_2_8,7);
Node c_2_5=new Node(null,c_2_7,5);
/**
* 构造第二课二叉树(测试3)
*/
Node c_3_9=new Node(9);
Node c_3_8=new Node(null,c_3_9,8);
Node c_3_7=new Node(null,c_3_8,7);
/**
* 构造第二课二叉树(测试4)
*/
Node c_4_20=new Node(20);
Node c_4_12=new Node(12);
Node c_4_18=new Node(null,null,18);
Node c_4_15=new Node(c_4_12,c_4_18,15);
/**
* 构造第二课二叉树(测试5)
*/
Node c_5_6=new Node(6);
Node c_5_7=new Node(c_5_6,null,7);
Node c_5_5=new Node(null,c_5_7,5);
Node c_5_12=new Node(12);
Node c_5_18=new Node(18);
Node c_5_15=new Node(c_5_12,c_5_18,15);
Node c_5_10=new Node(c_5_5,c_5_15,10);
compare=c_5_10;
/**
* 层次遍历
*/
boolean c=pre(root,compare);
System.out.println(c);
}
/**
* 先序遍历
* head 主二叉树
* compare 要比较的子树
*/
public static boolean pre(Node head,Node compare) {
if(head!=null) {
if(preCompare(head,compare))
return true;
if(head.left!=null)
if(pre(head.left,compare))
return true;
if(head.right!=null)
if(pre(head.right,compare))
return true;
}
return false;
}
/**
* 先序遍历子树进行比较
*/
public static boolean preCompare(Node h,Node c) {
if(h!=null&&c!=null) {
boolean b=true;
if(h.data!=c.data)
return false;
if(c.left!=null&&h.left==null)
return false;
if(h.left!=null&&c.left!=null)
if(!preCompare(h.left,c.left))
return false;
if(c.right!=null&&h.right==null)
return false;
if(h.right!=null&&c.right!=null)
b = preCompare(h.right,c.right);
return b;
}else {
return false;
}
}
}
评论区
请写下您的评论...
猜你喜欢
blog
数据结构-算法-完全二叉树的权值
数据结构与算法
5912
试题描述:思路:用数组表示完全二叉树,用先序遍历的方式遍历每一层的节点,用一个数组储存每一层的和,因为数据规模小于100000所以用一个容量为17的数组即可。计算完每一层的和,再比较层数最小之和最大
ofc
平衡二叉树
official
1145
leetcode第110题(简单)原链接https://leetcode-cn.com/problems/balanced-binary-tree/题目描述给定一个二叉树,判断它是否是高度平衡的二叉
weblog
6118
什么是二叉树的前驱节点和后继节点?某节点的前驱节点的val值小于该节点的val值并且值是最大的那个节点。某节点的后继节点的val值大于该节点的val值并且值是最小的那个节点。下面给出一个二叉树节点类
数据结构与算法
8375
)java代码实现importjava.util.LinkedList;/***二叉树结点类*@author硅谷探秘者(jia)*/classNode{ publicintdata; publicNodele
blog
二叉树的遍历-(递归法)和(非递归法)
数据结构与算法
5297
整理二叉树的遍历-(递归法)和(非递归法)-笔记先序遍历、中序遍历、后续遍历、层级遍历。1.节点信息:packagetree;publicclassNodeE{ privateEe;//数据域
ofc
二叉树中的列表
official
1354
叉树和一个head为第一个节点的链表。如果在二叉树中,存在一条一直向下的路径,且每个点的数值恰好一一对应以head为首的链表中每个节点的值,那么请你返回True,否则返回False。一直向下的路径的意思
blog
二叉树的一些性质
数据结构与算法
3846
转载:https://www.cnblogs.com/willwu/p/6007555.html1.树的定义树是一种数据结构,它是由n(n=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是
ofc
二叉树的所有路径
official
1214
径。说明:叶子节点是指没有子节点的节点。示例:输入:1/\23\5输出:["1-2-5","1-3"]解释:所有根节点到叶子节点的路径为:1-2-5,1-3解题思路递归得方式遍历二叉树(深度优先搜索),
最新发表
归档
2018-11
12
2018-12
33
2019-01
28
2019-02
28
2019-03
32
2019-04
27
2019-05
33
2019-06
6
2019-07
12
2019-08
12
2019-09
21
2019-10
8
2019-11
15
2019-12
25
2020-01
9
2020-02
5
2020-03
16
2020-04
4
2020-06
1
2020-07
7
2020-08
13
2020-09
9
2020-10
5
2020-12
3
2021-01
1
2021-02
5
2021-03
7
2021-04
4
2021-05
4
2021-06
1
2021-07
7
2021-08
2
2021-09
8
2021-10
9
2021-11
16
2021-12
14
2022-01
7
2022-05
1
2022-08
3
2022-09
2
2022-10
2
2022-12
5
2023-01
3
2023-02
1
2023-03
4
2023-04
2
2023-06
3
2023-07
4
2023-08
1
2023-10
1
2024-02
1
2024-03
1
2024-04
1
2024-08
1
标签
算法基础
linux
前端
c++
数据结构
框架
数据库
计算机基础
储备知识
java基础
ASM
其他
深入理解java虚拟机
nginx
git
消息中间件
搜索
maven
redis
docker
dubbo
vue
导入导出
软件使用
idea插件
协议
无聊的知识
jenkins
springboot
mqtt协议
keepalived
minio
mysql
ensp
网络基础
xxl-job
rabbitmq
haproxy
srs
音视频
webrtc
javascript
加密算法
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。