1 题目
假设二叉树采用二叉链表存储结构,设计一个算法求其指定的第k层(k>1,跟是第1层)的叶子结点个数。
2 思路
2.1 思路1
设置一个全局变量记录某层叶子结点个数,前序遍历二叉树,并在遍历的过程中记录结点的层数。
2.2 思路2
层序遍历二叉树,记录某层的二叉树叶子结点个数。没有目标层时,让该层结点的孩子结点入队;到达目标层时,不再让该层的孩子结点入队,统计队中(该层)叶子结点的个数。
- 具体流程
- 设置两个指针分别指该层的最后一个结点lastNode(初始为根结点)和下一层的最后一个非叶结点newNode。
- 每遍历到结点的左/右孩子为非叶结点时,把newNode更新为当前结点的左/右孩子;
- 当遍历的结点为该层的最后结点时,把lastNode更新为最新的newNode。
3 代码实现
二叉树的存储结构:
template <typename T>
class BiTNode {
public:
T data;
BiTNode* left;
BiTNode* right;
BiTNode():data(NULL),left(NULL),right(NULL){};
};
template <>
class BiTNode<int> {
public:
int data;
BiTNode* left;
BiTNode* right;
BiTNode() : data(0), left(nullptr), right(nullptr) {}
BiTNode(int x) : data(x), left(nullptr), right(nullptr) {}
BiTNode(int x, BiTNode *left, BiTNode *right) : data(x), left(left), right(right) {}
};
template <>
class BiTNode<char> {
public:
char data;
BiTNode* left;
BiTNode* right;
BiTNode() : data('\0'), left(nullptr), right(nullptr) {}
BiTNode(char x) : data(x), left(nullptr), right(nullptr) {}
BiTNode(char x, BiTNode *left, BiTNode *right) : data(x), left(left), right(right) {}
};
3.1 思路1
template <typename T>
void calLevelLeaf(BiTNode<T>* root, int level, int k){
if(level < k){
if(root->left != nullptr) calLevelLeaf(root->left, level+1, k);
if(root->right != nullptr) calLevelLeaf(root->right, level+1, k);
}else if(level == k && root->left == nullptr && root->right == nullptr){
leafNum++;
}
}
template <typename T>
int getLevelLeaf(BiTNode<T>* root, int k){
calLevelLeaf(root, 1, k);
return leafNum;
}
3.2 思路2
template <typename T>
int getLevelLeaf2(BiTNode<T>* root, int k){
deque<BiTNode<T>*> q;//双端队列
BiTNode<T> *newNode = nullptr, *lastNode = root;
int level = 1;//层数
int leafNum = 0;//该层的叶子结点个数
q.push_back(root);
while(!q.empty()){
BiTNode<T>* p;
if(level == k){
while(!q.empty()){
p = q.front();
q.pop_front();
if(p->left == nullptr && p->right == nullptr){
leafNum++;
}
}
break;
}
else{
p = q.front();
q.pop_front();
if(p->left != nullptr){
q.push_back(p->left);
newNode = p->left;
}
if(p->right != nullptr){
q.push_back(p->right);
newNode = p->right;
}
if(lastNode == p){
lastNode = newNode;
level += 1;
}
}
}
return leafNum;
}
3.3 完整的代码案例
#include <iostream>
#include <stack>
#include <deque>
#include <queue>
using namespace std;
template <typename T>
class BiTNode {
public:
T data;
BiTNode* left;
BiTNode* right;
BiTNode():data(NULL),left(NULL),right(NULL){};
};
template <>
class BiTNode<int> {
public:
int data;
BiTNode* left;
BiTNode* right;
BiTNode() : data(0), left(nullptr), right(nullptr) {}
BiTNode(int x) : data(x), left(nullptr), right(nullptr) {}
BiTNode(int x, BiTNode *left, BiTNode *right) : data(x), left(left), right(right) {}
};
template <>
class BiTNode<char> {
public:
char data;
BiTNode* left;
BiTNode* right;
BiTNode() : data('\0'), left(nullptr), right(nullptr) {}
BiTNode(char x) : data(x), left(nullptr), right(nullptr) {}
BiTNode(char x, BiTNode *left, BiTNode *right) : data(x), left(left), right(right) {}
};
template <typename T>
void createBiTNode(BiTNode<T>** treeNode, deque<T>dataDeq) {//层序遍历建立二叉树
//特殊处理根结点
T data;
data = dataDeq.front();
dataDeq.pop_front();
BiTNode<T> * node = new BiTNode<T>();
*treeNode = node;
(*treeNode)->data = data;
deque<BiTNode<T>**> nodeDeq;//用于层序建立树时访问双亲节点
nodeDeq.push_back(treeNode);
int index = 2;//用于判定左右孩子(左偶,右奇)
while (!dataDeq.empty()){//当数据节点非空时,进行建树
BiTNode<T>** nodeParent = nodeDeq.front();
nodeDeq.pop_front();
for(int i = 0; i < 2;i++){
data = dataDeq.front();
dataDeq.pop_front();
if(data == '#'){//适用于char
//if(data == -1){//适用于int
if(index%2 == 0) (*nodeParent)->left = nullptr;
else (*nodeParent)->right = nullptr;
}else{
BiTNode<T> * node = new BiTNode<T>();
node->data = data;
if(index%2 == 0){
(*nodeParent)->left = node;
nodeDeq.push_back(&(*nodeParent)->left);
}else{
(*nodeParent)->right = node;
nodeDeq.push_back(&(*nodeParent)->right);
}
}
index++;
}
}
}
template <>
void createBiTNode<char>(BiTNode<char>** treeNode, deque<char>dataDeq) {//层序遍历建立二叉树
//特殊处理根结点
char data;
data = dataDeq.front();
dataDeq.pop_front();
BiTNode<char> * node = new BiTNode<char>();
*treeNode = node;
(*treeNode)->data = data;
deque<BiTNode<char>**> nodeDeq;//用于层序建立树时访问双亲节点
nodeDeq.push_back(treeNode);
int index = 2;//用于判定左右孩子(左偶,右奇)
while (!dataDeq.empty()){//当数据节点非空时,进行建树
BiTNode<char>** nodeParent = nodeDeq.front();
nodeDeq.pop_front();
for(int i = 0; i < 2;i++){
data = dataDeq.front();
dataDeq.pop_front();
if(data == '#'){
if(index%2 == 0) (*nodeParent)->left = nullptr;
else (*nodeParent)->right = nullptr;
}else{
BiTNode<char> * node = new BiTNode<char>();
node->data = data;
if(index%2 == 0){
(*nodeParent)->left = node;
nodeDeq.push_back(&(*nodeParent)->left);
}else{
(*nodeParent)->right = node;
nodeDeq.push_back(&(*nodeParent)->right);
}
}
index++;
}
}
}
template <>
void createBiTNode<int>(BiTNode<int>** treeNode, deque<int>dataDeq) {//层序遍历建立二叉树
//特殊处理根结点
char data;
data = dataDeq.front();
dataDeq.pop_front();
BiTNode<int> * node = new BiTNode<int>();
*treeNode = node;
(*treeNode)->data = data;
deque<BiTNode<int>**> nodeDeq;//用于层序建立树时访问双亲节点
nodeDeq.push_back(treeNode);
int index = 2;//用于判定左右孩子(左偶,右奇)
while (!dataDeq.empty()){//当数据节点非空时,进行建树
BiTNode<int>** nodeParent = nodeDeq.front();
nodeDeq.pop_front();
for(int i = 0; i < 2;i++){
data = dataDeq.front();
dataDeq.pop_front();
if(data == -1){
if(index%2 == 0) (*nodeParent)->left = nullptr;
else (*nodeParent)->right = nullptr;
}else{
BiTNode<int> * node = new BiTNode<int>();
node->data = data;
if(index%2 == 0){
(*nodeParent)->left = node;
nodeDeq.push_back(&(*nodeParent)->left);
}else{
(*nodeParent)->right = node;
nodeDeq.push_back(&(*nodeParent)->right);
}
}
index++;
}
}
}
template <typename T>
void inOrder(BiTNode<T>* treeNode){
if(treeNode){
inOrder(treeNode->left);
cout<<treeNode->data<<" ";
inOrder(treeNode->right);
}
}
template <typename T>
void preOrder(BiTNode<T>* treeNode){
if(treeNode){
cout<<treeNode->data<<" ";
preOrder(treeNode->left);
preOrder(treeNode->right);
}
}
template <typename T>
void postOrder(BiTNode<T>* treeNode){
if(treeNode){
postOrder(treeNode->left);
postOrder(treeNode->right);
cout<<treeNode->data<<" ";
}
}
template <typename T>
void preOrder2(BiTNode<T>* treeNode){
stack<BiTNode<T>*> s;
BiTNode<T>* p = treeNode;
while(p || !s.empty()){
if(p){
cout<<p->data<<" ";
s.push(p);
p = p->left;
}else{
p = s.top();
s.pop();
p = p->right;
}
}
}
template <typename T>
void inOrder2(BiTNode<T>* treeNode){
stack<BiTNode<T>*> s;
BiTNode<T>* p = treeNode;
while(p || !s.empty()){
if(p){
s.push(p);
p = p->left;
}else{
p = s.top();
cout<<p->data<<" ";
s.pop();
p = p->right;
}
}
}
template <typename T>
void postOrder2(BiTNode<T>* treeNode){
stack<BiTNode<T>*> s;
BiTNode<T> *p = treeNode, *r = nullptr;
while(p || !s.empty()){
if(p){
s.push(p);
p = p->left;
}else{
p = s.top();
if(p->right && p->right != r){//有右孩子且没有访问过
p = p->right;
}else{
cout<<p->data<<" ";
s.pop();
r = p;
p = nullptr;
}
}
}
}
template <typename T>
void levelOrder(BiTNode<T>* treeNode) {
queue<BiTNode<T>*> nodeQue;
BiTNode<T>* p = treeNode;
nodeQue.push(p);
while(!nodeQue.empty()){
p = nodeQue.front();
nodeQue.pop();
cout<<p->data<<" ";
if(p->left) nodeQue.push(p->left);
if(p->right) nodeQue.push(p->right);
}
}
int leafNum = 0;
template <typename T>
void calLevelLeaf(BiTNode<T>* root, int level, int k){
if(level < k){
if(root->left != nullptr) calLevelLeaf(root->left, level+1, k);
if(root->right != nullptr) calLevelLeaf(root->right, level+1, k);
}else if(level == k && root->left == nullptr && root->right == nullptr){
leafNum++;
}
}
template <typename T>
int getLevelLeaf(BiTNode<T>* root, int k){
calLevelLeaf(root, 1, k);
return leafNum;
}
template <typename T>
int getLevelLeaf2(BiTNode<T>* root, int k){
deque<BiTNode<T>*> q;//双端队列
BiTNode<T> *newNode = nullptr, *lastNode = root;
int level = 1;//层数
int leafNum = 0;//该层的叶子结点个数
q.push_back(root);
while(!q.empty()){
BiTNode<T>* p;
if(level == k){
while(!q.empty()){
p = q.front();
q.pop_front();
if(p->left == nullptr && p->right == nullptr){
leafNum++;
}
}
break;
}
else{
p = q.front();
q.pop_front();
if(p->left != nullptr){
q.push_back(p->left);
newNode = p->left;
}
if(p->right != nullptr){
q.push_back(p->right);
newNode = p->right;
}
if(lastNode == p){
lastNode = newNode;
level += 1;
}
}
}
return leafNum;
}
int main() {
//使用字符串
//deque<char> treeVec{'a', 'b', 'c', 'd', 'e', '#', '#'};
//deque<char> treeVec{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', '#', '#','i','#','#','k','l'};
deque<char> treeVec{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', '#', 'i', 'j','#','#','k','l','m','n','#','#','o','#','#','p','#','#'};
BiTNode<char>* tree = new BiTNode<char>();
createBiTNode(&tree, treeVec);
//使用数值
// deque<int> treeVec{1, 2, 3, 4, 5, -1, -1};
// BiTNode<int>* tree = new BiTNode<int>();
// createBiTNode(&tree, treeVec);
//遍历树
//inOrder(tree);
//cout<<endl;
printf("%d", getLevelLeaf2(tree, 5));//tree,4
return 0;
}