数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程语言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中找到二叉树最近的叶节点
假设给定一棵二叉树。它在不同级别有叶节点。指针指向一个节点。我们必须找到从指向节点到最近叶节点的距离。考虑树如下所示——
此处叶节点为 2、-2 和 6。如果指针指向节点 -5，则与 -5 最近的节点距离为 1。
为了解决这个问题，我们将遍历给定节点根系的子树，并在子树中找到最靠近它的叶子，然后存储距离。现在从根开始遍历树，如果节点 x 存在于左子树中，则在右子树中搜索，反之亦然。
示例
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
Node* getNode(int data) {
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
void getLeafDownward(Node *root, int level, int *minDist) {
if (root == NULL)
return ;
if (root->left == NULL && root->right == NULL) {
if (level < (*minDist))
*minDist = level;
return;
}
getLeafDownward(root->left, level+1, minDist);
getLeafDownward(root->right, level+1, minDist);
}
int getFromParent(Node * root, Node *x, int *minDist) {
if (root == NULL)
return -1;
if (root == x)
return 0;
int l = getFromParent(root->left, x, minDist);
if (l != -1) {
getLeafDownward(root->right, l+2, minDist);
return l+1;
}
int r = getFromParent(root->right, x, minDist);
if (r != -1) {
getLeafDownward(root->left, r+2, minDist);
return r+1;
}
return -1;
}
int minimumDistance(Node *root, Node *x) {
int minDist = INT8_MAX;
getLeafDownward(x, 0, &minDist);
getFromParent(root, x, &minDist);
return minDist;
}
int main() {
Node* root = getNode(4);
root->left = getNode(2);
root->right = getNode(-5);
root->right->left = getNode(-2);
root->right->right = getNode(6);
Node *x = root->right;
cout << "Closest distance of leaf from " << x->data <<" is: " << minimumDistance(root, x);
}输出
Closest distance of leaf from -5 is: 1
更新于: 19-Dec-2019
234 次浏览
广告