数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法学在 C++ 中查找二叉树中根到给定结点的距离
考虑一下，我们有一个具有少量结点的二叉树。我们必须查找根与另一个结点 u 之间的距离。假设树如下所示
现在 (root, 6) 之间的距离 = 2，路径长度为 2，(root, 8) 之间的距离 = 3 等。
为了解决这个问题，我们将使用递归方法在左子树和右子树中搜索结点，并且还将更新每个级别的长度。
范例
#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;
}
int getDistance(Node *root, int x) {
if (root == NULL)
return -1;
int dist = -1;
if ((root->data == x) || (dist = getDistance(root->left, x)) >= 0 || (dist = getDistance(root->right, x)) >= 0)
return dist + 1;
return dist;
}
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 from root to node 6 is: " << getDistance(root,6);
cout << "\nDistance from root to node 8 is: " << getDistance(root,8);
}输出
Distance from root to node 6 is: 2 Distance from root to node 8 is: 3
更新于: 19-Dec-2019
312 浏览
广告