数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 C++ 程序中查找二叉树中两个节点之间的距离
在这个问题中，我们给定一棵二叉树和两个节点。我们的任务是创建一个程序来查找二叉树中两个节点之间的距离。
问题描述
我们需要找到两个节点之间的距离，即从一个节点到另一个节点遍历的最小边数。
让我们举个例子来理解这个问题，
输入：二叉树
节点1 = 3，节点2 = 5
输出: 3
解释
从节点 3 到节点 5 的路径是 3 -> 1 -> 2 -> 5。遍历了 3 条边，距离为 3。
解决方案
解决此问题的一个简单方法是使用给定节点的最近公共祖先节点，然后应用以下公式：
distance(node1, node2) = distance(root, node1) + distance(root, node2) + distance(root, LCA)
示例
#include <iostream>
using namespace std;
struct Node{
struct Node *left, *right;
int key;
};
Node* insertNode(int key){
Node *temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
int calcNodeLevel(Node *root, int val, int level) {
if (root == NULL)
return -1;
if (root->key == val)
return level;
int lvl = calcNodeLevel(root->left, val, level+1);
return (lvl != -1)? lvl : calcNodeLevel(root->right, val, level+1);
}
Node *findDistanceRec(Node* root, int node1, int node2, int &dist1, int &dist2, int &dist, int lvl){
if (root == NULL) return NULL;
if (root->key == node1){
dist1 = lvl;
return root;
}
if (root->key == node2){
dist2 = lvl;
return root;
}
Node *leftLCA = findDistanceRec(root->left, node1, node2, dist1,dist2, dist, lvl+1);
Node *rightLCA = findDistanceRec(root->right, node1, node2, dist1,dist2, dist, lvl+1);
if (leftLCA && rightLCA){
dist = dist1 + dist2 - 2*lvl;
return root;
}
return (leftLCA != NULL)? leftLCA: rightLCA;
}
int CalcNodeDistance(Node *root, int node1, int node2) {
int dist1 = -1, dist2 = -1, dist;
Node *lca = findDistanceRec(root, node1, node2, dist1, dist2, dist, 1);
if (dist1 != -1 && dist2 != -1)
return dist;
if (dist1 != -1){
dist = calcNodeLevel(lca, node2, 0);
return dist;
}
if (dist2 != -1){
dist = calcNodeLevel(lca, node1, 0);
return dist;
}
return -1;
}
int main(){
Node * root = insertNode(1);
root->left = insertNode(2);
root->right = insertNode(3);
root->left->left = insertNode(4);
root->left->right = insertNode(5);
root->right->left = insertNode(6);
cout<<"Distance between node with value 5 and node with value 3 is"<<CalcNodeDistance(root, 3, 5);
return 0;
}输出
Distance between node with value 5 and node with value 3 is 3
更新于：2020年10月9日
206 次查看
广告