資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢 Binary Tree 中兩個節點之間的距離
考慮我們有一個包含幾個節點的二叉樹。我們必須找出兩個節點 u 和 v 之間的距離。假設該樹如下所示 −
現在，(4, 6) 之間的距離 = 4，路徑長度為 4，(5, 8) 之間的長度 = 5，依此類推。
為了解決此問題，我們將找到 LCA（最低公共祖先），然後計算從 LCA 到兩個節點的距離。
示例
#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;
}
Node* LowestCommonAncestor(Node * root, int n1,int n2) {
if (root == NULL)
return root;
if (root->data == n1 || root->data == n2)
return root;
Node* left = LowestCommonAncestor(root->left, n1, n2);
Node* right = LowestCommonAncestor(root->right, n1, n2);
if (left != NULL && right != NULL)
return root;
if (left != NULL)
return LowestCommonAncestor(root->left, n1, n2);
return LowestCommonAncestor(root->right, n1, n2);
}
int getLevel(Node *root, int k, int level) {
if(root == NULL) return -1;
if(root->data == k) return level;
int left = getLevel(root->left, k, level+1);
if (left == -1)
return getLevel(root->right, k, level+1);
return left;
}
int findDistance(Node* root, int a, int b) {
Node* lca = LowestCommonAncestor(root, a , b);
int dist1 = getLevel(lca, a, 0);
int dist2 = getLevel(lca, b, 0);
return dist1 + dist2;
}
int main() {
Node* root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->right->left = getNode(6);
root->right->right = getNode(7);
root->right->left->right = getNode(8);
cout << "Distance between (4, 6) is: " << findDistance(root, 4, 6);
cout << "\nDistance between (8, 5) is: " << findDistance(root, 8, 5);
}輸出
Distance between (4, 6) is: 4 Distance between (8, 5) is: 5
更新於： 19-12-2019
168 次瀏覽
廣告