首页 > 代码库 > IT公司100题-11-求二叉树中节点的最大距离
IT公司100题-11-求二叉树中节点的最大距离
问题描述：
写程序，求一棵二叉树中相距最远的两个节点之间的距离。
10
/ \
6 14
/ \ / \
4 8 12 16
/ \
6 14
/ \ / \
4 8 12 16
分析：
二叉树中最远的两个节点，要么是根和一个叶子节点，要么是两个叶子节点。
代码实现：
1 // 11.cc 2 #include <iostream> 3 using namespace std; 4 5 typedef struct BSTreeNode { 6 int data; 7 BSTreeNode *left; 8 BSTreeNode *right; 9 } tree_node;10 11 // 创建二元查找树12 void add_BSTree_node(tree_node* &p_current, int data) {13 if (NULL == p_current) {14 tree_node *node = new tree_node();15 node->left = NULL;16 node->right = NULL;17 node->data =http://www.mamicode.com/ data;18 p_current = node;19 } else {20 if (p_current->data > data)21 add_BSTree_node(p_current->left, data);22 else if (p_current->data < data)23 add_BSTree_node(p_current->right, data);24 else25 cout << "The data has already in the tree.";26 }27 }28 29 int helper(tree_node* root, int& depth) {30 if (!root) {31 depth = 0;32 return 0;33 }34 int ld, rd;35 int max_left = helper(root->left, ld);36 int max_right = helper(root->right, rd);37 depth = max(ld, rd) + 1;38 return max(max_left, max(max_right, ld + rd));39 }40 41 // 查找最大距离42 int max_distance(tree_node* root) {43 int depth;44 return helper(root, depth);45 }46 47 int main() {48 tree_node *root = NULL;49 add_BSTree_node(root, 10);50 add_BSTree_node(root, 2);51 add_BSTree_node(root, 4);52 add_BSTree_node(root, 6);53 add_BSTree_node(root, 8);54 add_BSTree_node(root, 12);55 add_BSTree_node(root, 14);56 add_BSTree_node(root, 16);57 58 int depth;59 int max_d = max_distance(root);60 cout << max_d << endl;61 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。