数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究用 C++ 打印二叉树中所有距离叶子节点 K 个距离的节点
在这个问题中，我们给定一棵二叉树和一个数字 K。我们必须打印树中所有距离叶子节点 K 个距离的节点。
二叉树是一种特殊的树，其每个节点最多有两个子节点（一个/两个/没有）。
叶子节点是二叉树末端的节点。
在这个问题中，距离叶子节点的距离是指比叶子节点高一级的节点。假设，距离叶子节点 2 个距离的节点在第 4 层，那么它将在第 2 层。
让我们举一个例子来理解这个问题
K = 2
输出 - 6 9。
为了解决这个问题，我们将遍历树。所有存储所有父节点集（也称为祖先节点）逐层，直到到达叶子节点。现在，我们将打印距离叶子节点 K 个距离的祖先。在遍历过程中，标记已访问的节点非常重要以避免重复，我们将使用一个布尔数组来实现这一点 -
由于代码仅使用树遍历，因此复杂度与 n 成正比。时间复杂度：O(n)
示例
程序来说明我们的逻辑 -
#include <iostream>
using namespace std;
#define MAX_HEIGHT 10000
struct Node {
int key;
Node *left, *right;
};
Node* insertNode(int key){
Node* node = new Node;
node->key = key;
node->left = node->right = NULL;
return (node);
}
void nodesKatDistance(Node* node, int path[], bool visited[], int pathLen, int k){
if (node==NULL) return;
path[pathLen] = node->key;
visited[pathLen] = false;
pathLen++;
if (node->left == NULL && node->right == NULL && pathLen-k-1 >= 0 && visited[pathLen-k-1] == false){
cout<<path[pathLen-k-1]<<"\t";
visited[pathLen-k-1] = true;
return;
}
nodesKatDistance(node->left, path, visited, pathLen, k);
nodesKatDistance(node->right, path, visited, pathLen, k);
}
void printNodes(Node* node, int k){
int path[MAX_HEIGHT];
bool visited[MAX_HEIGHT] = {false};
nodesKatDistance(node, path, visited, 0, k);
}
int main(){
Node * root = insertNode(6);
root->left = insertNode(3);
root->right = insertNode(9);
root->left->right = insertNode(4);
root->right->left = insertNode(8);
root->right->right = insertNode(10);
root->right->left->left = insertNode(5);
root->right->left->right = insertNode(1);
int k = 2 cout<<"All nodes at distance "<<k<<" from leaf node are:\n";
printNodes(root, k);
return 0;
}输出
距离叶子节点 2 个距离的所有节点为 -
6 9
更新于： 2020-01-22
158 次查看
广告