剑指offer十七姊妹篇之二叉树的创建、遍历、判断子二叉树
2024-08-26 01:31:36
1、二叉树节点类
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
//----------------------------
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
2、二叉树打印类
public class PrintTree {
public void printNode(TreeNode node){
System.out.print(node.getVal());
}
//先序遍历
public void theFirstTraversal(TreeNode root) {
printNode(root);
if (root.getLeft() != null) { //使用递归进行遍历左孩子
theFirstTraversal(root.getLeft());
}
if (root.getRight() != null) { //递归遍历右孩子
theFirstTraversal(root.getRight());
}
}
//中序遍历
public void theInOrderTraversal(TreeNode root) {
if (root.getLeft() != null) {
theInOrderTraversal(root.getLeft());
}
printNode(root);
if (root.getRight() != null) {
theInOrderTraversal(root.getRight());
}
}
//后序遍历
public void thePostOrderTraversal(TreeNode root) {
if (root.getLeft() != null) {
thePostOrderTraversal(root.getLeft());
}
if(root.getRight() != null) {
thePostOrderTraversal(root.getRight());
}
printNode(root);
}
}
3、判断二叉树是否包含另一棵树的类
public class HasSubtree {
public boolean hasSubtree(TreeNode root1, TreeNode root2) {
boolean result = false;
//当Tree1和Tree2都不为零的时候，才进行比较。否则直接返回false
if (root2 != null && root1 != null) {
//如果找到了对应Tree2的根节点的点
if (root1.val == root2.val) {
//以这个根节点为为起点判断是否包含Tree2
result = doesTree1HaveTree2(root1, root2);
}
//如果找不到，那么就再去root的左叶子当作起点，去判断时候包含Tree2
if (!result) {
result = hasSubtree(root1.left, root2);
}
//如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2
if (!result) {
result = hasSubtree(root1.right, root2);
}
}
//返回结果
return result;
}
public static boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {
//如果Tree2已经遍历完了都能对应的上，返回true
if (node2 == null) {
return true;
}
//如果Tree2还没有遍历完，Tree1却遍历完了。返回false
if (node1 == null) {
return false;
}
//如果其中有一个点没有对应上，返回false
if (node1.val != node2.val) {
return false;
}
//如果根节点对应的上，那么就分别去子节点里面匹配
return doesTree1HaveTree2(node1.left, node2.left) && doesTree1HaveTree2(node1.right, node2.right);
}
}
4、测试类
public class TestMain {
public static void main(String[] args) {
//创建二叉树tree1
TreeNode root1=new TreeNode(0);
TreeNode node11=new TreeNode(1);
TreeNode node12=new TreeNode(2);
TreeNode node13=new TreeNode(3);
TreeNode node14=new TreeNode(4);
TreeNode node15=new TreeNode(5);
TreeNode node16=new TreeNode(6);
root1.setLeft(node11);
root1.setRight(node12);
node11.setLeft(node13);
node11.setRight(node14);
node12.setLeft(node15);
node12.setRight(node16);
//采用前序遍历方式打印二叉树
PrintTree p=new PrintTree();
p.theFirstTraversal(root1);
System.out.println();
//创建二叉树tree2
TreeNode root2=new TreeNode(1);
TreeNode node21=new TreeNode(3);
TreeNode node22=new TreeNode(4);
root2.setLeft(node21);
root2.setRight(node22);
//采用前序遍历方式打印二叉树
PrintTree p2=new PrintTree();
p2.theFirstTraversal(root2);
System.out.println();
//判断tree2是否为tree1的子树
HasSubtree h=new HasSubtree();
Boolean b=h.hasSubtree(root1,root2);
System.out.println("是否包含："+b);
}
}
最新文章
- NTP服务器引起的上行带宽超大
- [LeetCode]题解（python）：112 Path Sum
- JavaScript中的*top、*left、*width、*Height详解
- 0R电阻作用
- Qt：截图工具，任意大小矩形截图、全屏截图
- windows编程:创建DLL
- linux之sed的常用操作
- 团队作业8——第二次项目冲刺（Beta阶段）--第七天
- junit--eclipse插件
- DELL服务器硬件信息采集SHELL脚本
- jQuery在页面加载的时候自动调用某个函数的方法
- SolidWorks装配体
- flask 中使用 socket 遇到的坑
- IDEA+Tomcat+Maven+SpringMVC基于Java注解配置web工程
- HTML词法和语法
- python的进程/线程/协程
- 【慕课网实战】Spark Streaming实时流处理项目实战笔记二十一之铭文升级版
- Javascript 函数声明先提升还是变量先提升
- 26.pymysql、pymongo、redis-py安装
- Table折叠小技巧html-demo