c语言数据结构 二叉树（二）

一.关于二叉树的一些基本功能的实现

1.紧接上文博客遗留的问题，如何求二叉树第k层结点个数。

利用子问题解决，代码实现如下所示

2.在二叉树中找到数据为x的结点并返回

利用子问题来解决 

时间复杂度为O(N)

二.有关二叉树的OJ题讲解

1.单值二叉树的判断

题目要求：

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

例：

 代码如下：

2. 相同的树的判断

题目要求：

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

例：

 

 代码如下：

 3.另一棵树的子树

题目要求 ：

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

例：

代码如下：

 

4.二叉树前序遍历

题目要求：

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

 例：

OJ题目一般分为两种：接口型和IO型

代码实现如下所示