2.2计算叶子节点的个数
设计一个递归函数，计算一个二叉树叶子节点的个数。
我们还是借用之前的思路，将问题先缩小到一个小范围--一个根和它的左右子树，然后思考叶子节点的特点，很显然，就是叶子结点的左右子树都为NULL。明白了这一点，我们就着手写这个函数。
int TreeLeafSize(BTNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return TreeLeafSize(root->left) + TreeLeafSize(root->right); } int main() { BTNode* root= CreateBinaryTree(); int leafsize = TreeLeafSize(root); printf("%d ", leafsize); printf("\n"); return 0; }
2.3二叉树的高度
递归实现并返回二叉树的高度。
这个问题有点意思，我们还是要利用二叉树的结构特点来解这个问题，想一下，如果对于一个根和它的左右子树，我们一定是算左右子树高度，然后取较大的那个再加上根那一层。没错，这个递归也是基于这一理念。
int TreeHeight(BTNode* root) { if (root == NULL) return 0; int lh = TreeHeight(root->left); int rh = TreeHeight(root->right); return lh > rh ? lh + 1 : rh + 1;//加一是加上根 } int main() { BTNode* root= CreateBinaryTree(); int height = TreeHeight(root); printf("%d ", height); printf("\n"); return 0; }
2.4计算二叉树第K层节点个数
递归计算二叉树第K层节点的个数。
这个问题本质就是对第K层进行层序遍历，那么我们怎么找到第K层对它进行层序遍历呢？
我们假设一种极端情况，如果只有一个根，那么遍历很明显第1层就1个，于是就设计出这样一种思想：将第K层转换成左右子树的第K-1层，那么当K==1时，不就是只有一个根那种情况计算了？
int TreeKLevel(BTNode* root, int k) { if (root == NULL) return 0; if (k == 1) return 1; //转化为左右子树的第k-1层 return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1); } int main() { BTNode* root= CreateBinaryTree(); int Klevel = TreeKLevel(root, 4); printf("%d ", Klevel); printf("\n"); return 0; }
2.5二叉树查找值为x的节点
递归查找二叉树中值为x的节点。
还是那一招，借助二叉树的结构查找，很简单的设计思想，先去左子树查找，如果没有找到，那么就去右子树查找。
BTNode* TreeFind(BTNode* root, int x) { BTNode* lret, *rret; if (root == NULL) return NULL; if (root->data == x) return root; lret = TreeFind(root->left, x); if (lret) return lret; rret = TreeFind(root->right, x); if (rret) return rret; } int main() { BTNode* root= CreateBinaryTree(); BTNode* find = TreeFind(root, 7); if (find) printf("找到了，%d\n", find->data); else printf("没找到\n"); return 0; }
三、二叉树基础oj练习
3.1单值二叉树
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
示例：
缩小到一个根和它的左右子树。
1、如果遇到空，它被视为是正确的。
2、只有它的非空左右子树都等于根时才是true，但是正着写代码，比较麻烦，我们正难则反，如果不相等就为false。
bool isUnivalTree(struct TreeNode* root) { //每一个双亲和它孩子的值相等， //如果遇到空，被视为正确的 //双亲的左孩子和右孩子都应该保证它和它的左右孩子相等 if(root==NULL) return true; if(root->left&&root->left->val!=root->val)//左右子树不为NULL才有比较的意义 return false; if(root->right&&root->right->val!=root->val) return false; return isUnivalTree(root->left)&&isUnivalTree(root->right); }
3.2相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例：
对于这个题目，还是正难则反的思想，因为判断true所需的条件过多，而判断为false则很简单，因此要反着写。
bool isSameTree(struct TreeNode* p, struct TreeNode* q) { //先考虑特殊情况 if(p==NULL&&q==NULL)//都为空的情况，显然是true return true; if(p==NULL||q==NULL)//一个为空，一个不为空的情况，为false return false; if(p->val!=q->val) return false; else { return isSameTree(p->left,q->left)&& isSameTree(p->right,q->right); } }
3.3对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
如果理解了相同的树这道题目，这道题目应是不难的，只是换汤不换药。唯一的区别在于，相同，改为判断是否对称，那我们只需由原来的判断左子树是否等于左子树，和右子树是否等于右子树变为，左子树是否等于右子树，右子树是否等于左子树不就解决了？我们借用上面的函数，稍微更改一下，就解决了这道题目。
bool isSameTree(struct TreeNode* p, struct TreeNode* q) { if(p==NULL&& q==NULL) return true; if(p==NULL||q==NULL) return false; if(p->val!=q->val) return false; return isSameTree(p->left,q->right)&&isSameTree(p->right,q->left); //其中一个为NULL,另一个不为NULL } bool isSymmetric(struct TreeNode* root) { if(root==NULL) return true; return isSameTree(root->left,root->right); }
3.4另一个棵树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例：
这道题目，额，，，不还是相同的树的一种演变吗？我们还是可以直接拷过来用。只不过我们需判断，从根开始是否和另一个树相同，从左子树开始是否和另一个树相同，从右子树开始是否和另一个树相同。
不同的是要注意，如果根为空，那么另一个树不可能为它的子树。
bool isSameTree(struct TreeNode* root1, struct TreeNode* root2) { if(root1==NULL&&root2==NULL) return true; if(root1==NULL||root2==NULL) return false; if(root1->val!=root2->val) return false; else { return isSameTree(root1->left,root2->left) &&isSameTree(root1->right,root2->right); } } bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) { if(root==NULL) return false; if(isSameTree(root,subRoot)) return true; return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot); //因为左右子树只要有一个相同就行 }
3.5平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
这道题目，如果前面计算二叉树的高度掌握的话，相信也是小菜一碟。我们只需要计算根的左右子树的高度，然后计算差距高度，要求不超过1并且每个根都要满足这样的条件，所谓正难则反，我们反过来写超过1就给false，然后递归。
注意，根为空是满足条件的。
int TreeHeight(struct TreeNode* root) { if(root==NULL) return 0; int lh=TreeHeight(root->left); int rh=TreeHeight(root->right); return lh>rh?lh+1:rh+1; } bool isBalanced(struct TreeNode* root) { //直接计算高度 if(root==NULL) return true; int lh= TreeHeight(root->left); int rh=TreeHeight(root->right); //正难则反 int gap=lh-rh; if(gap<0) gap=-gap; if(gap>1) return false; else { return isBalanced(root->left)&&isBalanced(root->right); } }
3.6二叉树遍历
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
示例：
输入：
abc##de#g##f###
输出：
c b e g d f a
这道题目给出我们先序遍历的结果，需要我们根据先序遍历构建二叉树，然后中序遍历一次我们构建的二叉树，输出即可。所以我们需要解决的问题主要有两个
1、根据先序遍历构建二叉树
2、对二叉树进行中序遍历
①由先序遍历构建二叉树
单纯来想是不好想的，我们要反其道而行之，先序遍历的结果是如何得来的？
不就是对二叉树进行根-->左子树-->右子树的遍历方式得到的吗？所以我们对遍历的结果再进行同样的遍历去构建链接二叉树不就行了吗？
博主先把typedef的一些内容放在前面。
#include<stdio.h> #include<stdlib.h> typedef char BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode;
先序遍历重建二叉树代码：
BTNode* BTCreatePreOrder(char* a, int* pi) { if (a[*pi]=='#') { (*pi)++; return NULL; } BTNode* root = (BTNode*)malloc(sizeof(BTNode)); if (root == NULL) { perror("malloc fail"); exit(-1); } root->data = a[*pi]; (*pi)++; root->left = BTCreatePreOrder(a, pi); root->right = BTCreatePreOrder(a, pi); return root; } int main() { char TData[100] = { 0 }; while (scanf("%s", TData) != EOF) { int i = 0; BTNode* root=BTCreatePreOrder(TData, &i); InOrder(root); BTDestory(root); } }
IO型题目需要我们自己写main函数，不只是接口，这里有些细节还需要我们注意。
1、首先是为什么传i的地址？
这是因为，我们在递归重建二叉树的时候是会建立函数栈帧的，而如果我们传值，在函数返回的时候，变量销毁，是无法影响到外面的值，导致无法遍历字符数组的下一个。
2、不要忘记当我们遇到'#'的时候，字符数组需要++.
中序遍历二叉树以及释放空间
中序遍历前面博主有写过，这里不再赘述，需要注意我们重建二叉树，向堆申请了空间，所以我们需要遍历释放空间的。
void InOrder(BTNode* root) { if (root == NULL) { return; } InOrder(root->left); printf("%c ", root->data); InOrder(root->right); } void BTDestory(BTNode* root) { if (root == NULL) return; BTDestory(root->left); BTDestory(root->right); free(root); }
整体代码：
#include <stdio.h> #include<stdlib.h> typedef char BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; typedef char BTDataType; BTNode* BTCreatePreOrder(char* a, int* pi) { if (a[*pi]=='#') { (*pi)++; return NULL; } BTNode* root = (BTNode*)malloc(sizeof(BTNode)); if (root == NULL) { perror("malloc fail"); exit(-1); } root->data = a[*pi]; (*pi)++; root->left = BTCreatePreOrder(a, pi); root->right = BTCreatePreOrder(a, pi); return root; } void InOrder(BTNode* root) { if (root == NULL) { return; } InOrder(root->left); printf("%c ", root->data); InOrder(root->right); } void BTDestory(BTNode* root) { if (root == NULL) return; BTDestory(root->left); BTDestory(root->right); free(root); } int main() { char TData[100] = { 0 }; while (scanf("%s", TData) != EOF) { int i = 0; BTNode* root=BTCreatePreOrder(TData, &i); InOrder(root); BTDestory(root); } }
还原的二叉树：(方便读者印证)
对于之前博主提到的，前序+中序重建二叉树以及中序+后序重建二叉树的代码实现，由于需要用到一些高阶数据结构(哈希表等)以及C++的知识，因为博主目前实力有限，是个菜鸡，所以无法实现，日后补上。码文不易，希望各位支持哦！
