IT公司100题-11-求二叉树中节点的最大距离

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

问题描述：

写程序，求一棵二叉树中相距最远的两个节点之间的距离。

10
/ \
6 14
/ \ / \
4 8 12 16

分析：

二叉树中最远的两个节点，要么是根和一个叶子节点，要么是两个叶子节点。

代码实现：

// 11.cc
#include <iostream>
using namespace std; typedef struct BSTreeNode {
int data;
BSTreeNode *left;
BSTreeNode *right;
} tree_node; // 创建二元查找树
void add_BSTree_node(tree_node* &p_current, int data) {
if (NULL == p_current) {
tree_node *node = new tree_node();
node->left = NULL;
node->right = NULL;
node->data = data;
p_current = node;
} else {
if (p_current->data > data)
add_BSTree_node(p_current->left, data);
else if (p_current->data < data)
add_BSTree_node(p_current->right, data);
else
cout << "The data has already in the tree.";
}
} int helper(tree_node* root, int& depth) {
if (!root) {
depth = ;
return ;
}
int ld, rd;
int max_left = helper(root->left, ld);
int max_right = helper(root->right, rd);
depth = max(ld, rd) + ;
return max(max_left, max(max_right, ld + rd));
} // 查找最大距离
int max_distance(tree_node* root) {
int depth;
return helper(root, depth);
} int main() {
tree_node *root = NULL;
add_BSTree_node(root, );
add_BSTree_node(root, );
add_BSTree_node(root, );
add_BSTree_node(root, );
add_BSTree_node(root, );
add_BSTree_node(root, );
add_BSTree_node(root, );
add_BSTree_node(root, ); int depth;
int max_d = max_distance(root);
cout << max_d << endl;
}