数据结构和算法-判断一棵二叉树是否为另一颗二叉树的子树
题目:判断下方两棵二叉树右方的二叉树是否为左方二叉树的子树
例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
数据结构-算法-完全二叉树的权值
数据结构与算法
4976
试题描述:思路:用数组表示完全二叉树,用先序遍历的方式遍历每一层的节点,用一个数组储存每一层的和,因为数据规模小于100000所以用一个容量为17的数组即可。计算完每一层的和,再比较层数最小之和最大
ofc
平衡二叉树
official
398
leetcode第110题(简单)原链接https://leetcode-cn.com/problems/balanced-binary-tree/题目描述给定一个二叉树,判断它是否是高度平衡的二叉
weblog
3492
什么是二叉树的前驱节点和后继节点?某节点的前驱节点的val值小于该节点的val值并且值是最大的那个节点。某节点的后继节点的val值大于该节点的val值并且值是最小的那个节点。下面给出一个二叉树节点类
数据结构与算法
7496
)java代码实现importjava.util.LinkedList;/***二叉树结点类*@author硅谷探秘者(jia)*/classNode{ publicintdata; publicNodele
blog
二叉树的遍历-(递归法)和(非递归法)
数据结构与算法
4386
整理二叉树的遍历-(递归法)和(非递归法)-笔记先序遍历、中序遍历、后续遍历、层级遍历。1.节点信息:packagetree;publicclassNodeE{ privateEe;//数据域
ofc
二叉树中的列表
official
452
叉树和一个head为第一个节点的链表。如果在二叉树中,存在一条一直向下的路径,且每个点的数值恰好一一对应以head为首的链表中每个节点的值,那么请你返回True,否则返回False。一直向下的路径的意思
blog
二叉树的一些性质
数据结构与算法
2652
转载:https://www.cnblogs.com/willwu/p/6007555.html1.树的定义树是一种数据结构,它是由n(n=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是
ofc
二叉树的所有路径
official
424
径。说明:叶子节点是指没有子节点的节点。示例:输入: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月
1
标签
算法基础
linux
前端
c++
数据结构
框架
数据库
计算机基础
储备知识
java基础
ASM
其他
深入理解java虚拟机
nginx
git
消息中间件
搜索
maven
redis
docker
dubbo
vue
导入导出
软件使用
idea插件
协议
无聊的知识
jenkins
springboot
mqtt协议
keepalived
minio
目录
祝愿神州十三飞行乘组平安归来