資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告