标题: [Microsoft面试]求二叉树中节点的最大距离？ [打印本页] 作者: 王鹏 时间: 2013-8-16 10:42 标题: [Microsoft面试]求二叉树中节点的最大距离？ 如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。写一个程序，求一棵二叉树中相距最远的两个节点之间的距离。作者: 陈荣莲 时间: 2013-8-16 10:46
This isinteresting... Also recursively, the longest distance between two nodes must beeither from root to one leaf, or between two leafs. For the former case, it’sthe tree height. For the latter case, it should be the sum of the heights ofleft and right subtrees of the two leaves’ most least ancestor.The first case is also the sum the heights of subtrees, just the height + 0.intmaxDistance(Node * root) { int depth; return helper(root, depth);}int helper(Node * root, int &depth) { if (root == NULL) { depth = 0; return 0; } int ld, rd; int maxleft = helper(root->left, ld); int maxright = helper(root->right, rd); depth = max(ld, rd)+1; return max(maxleft, max(maxright, ld+rd));}