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