剑指Offer的学习笔记(C#篇)-- 树的子结构
2024-09-16 21:48:42
题目描述
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
一 . 二叉树的概念
树形结构是一种典型的非线性结构,除了用于表示相邻关系外,还可以表示层次关系。每个结点最多有两棵子树。左子树和右子树是有顺序的,次序不能任意颠倒。即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。即为下图。。
C#定义二叉树:
public class BinaryTreeNode
{
//节点
public int Data { get; set; }
//左子树
public BinaryTreeNode leftChild { get; set; }
//右子树
public BinaryTreeNode rightChild { get; set; }
//数据域
public BinaryTreeNode(int data)
{
this.Data = data;
}
//指针域
public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right)
{
this.Data = data;
this.leftChild = left;
this.rightChild = right;
}
}
二 . 题目分析
A-B两个二叉树,判断B是否为A的子结构。
想法:该题使用递归法。步骤为:在树A中找到和B的根结点的值一样的结点;判断以该节点为中心的左右子树是否相同,相同即为子结构,不同继续递归,直到结束。
三 . 代码实现:
class Solution
{
public bool HasSubtree(TreeNode pRoot1, TreeNode pRoot2)
{
// write code here
if(pRoot1 == null || pRoot2 == null)
{
return false;
}
else
{
return Judge(pRoot1,pRoot2);
}
}
public static bool Judge(TreeNode pRoot1, TreeNode pRoot2)
{
//解释说是pRoot2如果全部遍历完且与pRoot1一一对应,则返回正确
//如果pRoot2还没遍历完,而pRoot1已经遍历结束,则错误。
if (pRoot2 == null)
{
//递归成功条件,什么意思呢,比如B仅有一个节点,且存在和A一样的节点,那肯定是是咯
return true;
}
if (pRoot1 == null)
{
//递归失败条件,如果你一直递归下去,A都结束了,还没找到,那肯定不是咯。
return false;
}
if (pRoot1.val == pRoot2.val)
{
//递归成功条件2,左右节点都一样
if (Judge(pRoot1.left,pRoot2.left) && Judge(pRoot1.right,pRoot2.right))
{
return true;
}
}
//递归
return Judge(pRoot1.left,pRoot2) || Judge(pRoot1.right,pRoot2);
}
}
PS:该题考点依旧是代码的鲁棒性,所以要格外注意,其实貌似就这么一处吧if(pRoot1 == null || pRoot2 == null)。。
最新文章
- lnmp无法删除目录,目录包含.user.ini
- web报表工具FineReport常用函数的用法总结(报表函数)
- WPF DataGrid – Dynamically updating DataGridComboBoxColumn
- git的使用(二)
- 基于jQuery上下切换的焦点图—带缩略图悬浮
- 抛弃 CSS Hacks 后的浏览器兼容方案
- js 数组 var arr=[] 的用法总结
- linux无法umount解决方案
- (转)fastcgi协议的简单实现
- 对Lucene PhraseQuery的slop的理解[转载]
- 为什么要重写equals和hashCode
- JavaScript数组基础及实例
- Java基础学习笔记十七 集合框架(三)之Map
- [POJ2054]Color a Tree (并查集+贪心)
- 浅谈 R_S触发器
- 如何让微信里的html应用弹出“点击右上角分享到朋友圈”的图片
- java倒计时使用java.util.Timer实现,使用两个线程,以秒为单位
- mysql root密码修改
- python tornado异步性能测试
- ccttp图片处理过程
热门文章
- 构建工具是如何用 node 操作 html/js/css/md 文件的
- 《机器学习实战》学习笔记第二章 —— K-近邻算法
- Hadoop- NameNode和Secondary NameNode元数据管理机制
- python列表切片
- Android窗口系统第一篇---Window的类型与Z-Order确定
- 分享知识-快乐自己: Oracle数据库实例、用户、表、表空间之间关系
- next enum in swift
- 【Lintcode】011.Search Range in Binary Search Tree
- javacpp-FFmpeg系列补充:FFmpeg解决avformat_find_stream_info检索时间过长问题
- 关于Socket 多线程 的一篇好文章