数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究用 C++ 打印二叉树中具有 K 个叶子节点的所有节点
在这个问题中，我们给定一棵二叉树和一个整数 K，我们必须打印二叉树中所有在其子树中具有 K 个叶子节点的节点。
二叉树是一种特殊的树，其每个节点最多有两个子节点（一个/两个/零个）。
叶子节点是二叉树末端的节点。
让我们来看一个例子来理解这个问题：
K = 2
输出： {S}
为了解决这个问题，我们将对树进行遍历（后序遍历）。现在，我们将查看每个左子树和右子树，如果叶子节点之和为 K，则打印当前节点；否则递归调用子树的叶子节点计数。
此解决方案基于遍历，因此复杂度将与树的大小成正比。时间复杂度： O(n)
示例
实现上述方法的程序
#include<bits/stdc++.h>
using namespace std;
struct Node{
char data ;
struct Node * left, * right ;
};
struct Node * insertNode(char data){
struct Node * node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int nodeWithKLeave(struct Node *ptr,int k){
if (ptr == NULL)
return 0;
if (ptr->left == NULL && ptr->right == NULL)
return 1;
int total = nodeWithKLeave(ptr->left, k) + nodeWithKLeave(ptr->right, k);
if (k == total)
cout<<ptr->data<<" ";
return total;
}
int main() {
struct Node *root = insertNode('A');
root->left = insertNode('B');
root->right = insertNode('K');
root->left->left = insertNode('N');
root->left->right = insertNode('S');
root->left->left->left = insertNode('X');
root->left->left->right = insertNode('H');
root->right->right = insertNode('E');
root->right->left = insertNode('T');
root->right->left->left = insertNode('O');
root->right->left->right = insertNode('P');
int K = 2;
cout<<"Nodes with "<<K<<" leaves is :\n";
nodeWithKLeave(root, K);
return 0;
}输出
Nodes with 2 leaves are: N T
更新于：2020年1月22日
125 次浏览
广告