数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告