資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢二叉樹中最深節點
在這個問題中，我們給定一棵二叉樹。我們的任務是查詢二叉樹中最深的節點。
二叉樹是一種用於資料儲存的特殊資料結構。二叉樹有一個特殊條件，即每個節點最多可以有兩個子節點。
二叉樹中最深的節點是指樹中高度最大的節點。
讓我們舉一個例子來理解這個問題，
輸入
輸出：8
解決方案方法
解決此問題的方法有很多種，因為您需要找到高度並遍歷樹到高度的最後一個節點並返回它。所有解決方案都將僅基於此原理。在這裡，我們討論了一些有前景且經過最佳化的解決方案。
一個簡單的解決方案是使用樹的中序遍歷並維護一個級別標記，如果當前級別大於 maxLevel。我們將初始化節點為 deepestNode。遍歷完樹的所有節點後，我們將返回 deepestNode。對於樹的遍歷，我們將使用遞迴。
示例
程式說明我們解決方案的工作原理
#include <iostream>
using namespace std;
struct Node{
int data;
struct Node *left, *right;
};
Node *newNode(int data){
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void findDeepestNodeRec(Node *root, int currentLevel, int &maxLevel, int &deepestNode){
if (root != NULL){
findDeepestNodeRec(root->left, ++currentLevel, maxLevel, deepestNode);
if (currentLevel > maxLevel){
deepestNode = root->data;
maxLevel = currentLevel;
}
findDeepestNodeRec(root->right, currentLevel, maxLevel, deepestNode);
}
}
int findDeepestNodeBT(Node *root){
int deepestNode = 0;
int maxLevel = 0;
findDeepestNodeRec(root, 0, maxLevel, deepestNode);
return deepestNode;
}
int main(){
Node* root = newNode(3);
root->left = newNode(5);
root->right = newNode(4);
root->left->left = newNode(1);
root->left->right = newNode(9);
root->right->left = newNode(6);
root->right->left->right = newNode(8);
cout<<"The deepest node of the given binary tree is "<<findDeepestNodeBT(root);
return 0;
}輸出
The deepest node of the given binary tree is 8
另一種方法來解決問題是找到給定樹的高度。然後返回級別等於樹高度的節點。
示例
程式說明我們解決方案的工作原理
#include <bits/stdc++.h>
using namespace std;
struct Node{
int data; struct Node *left, *right;
};
Node *newNode(int data){
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int calcHeight(Node* root){
if(!root) return 0;
int leftHt = calcHeight(root->left) + 1;
int rightHt = calcHeight(root->right) + 1;
return max(leftHt, rightHt);
}
void findDeepestNodeBT(Node* root, int levels){
if(!root) return;
if(levels == 1)
cout << root->data;
else if(levels > 1){
findDeepestNodeBT(root->left, levels - 1);
findDeepestNodeBT(root->right, levels - 1);
}
}
int main(){
Node* root = newNode(3);
root->left = newNode(5);
root->right = newNode(4);
root->left->left = newNode(1);
root->left->right = newNode(9);
root->right->left = newNode(6);
root->right->left->right = newNode(8);
int maxHeight = calcHeight(root);
cout<<"The deepest node of the binary tree is ";
findDeepestNodeBT(root, maxHeight);
return 0;
}輸出
The deepest node of the binary tree is 8
更新於：2022-01-27
591 次瀏覽
廣告