第十一题（求二叉树中节点的最大距离）

本文主要是介绍第十一题（求二叉树中节点的最大距离），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第11 题
求二叉树中节点的最大距离...
如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，
我们姑且定义"距离"为两节点之间边的个数。
写一个程序，
求一棵二叉树中相距最远的两个节点之间的距离。

分析：

采用递归求解

对于一个根节点，取 左子树最大深度+右子树最大深度，左子树最大距离，右子树最大距离这三种情况的最大值，最大值就是所要求的节点的最大距离。

结束条件为：对于叶子节点，深度，最大距离都是0。

采用引用传递参数的方式，取得子树的深度，子树的最大距离通过返回值传递。

代码：

<pre name="code" class="cpp">namespace MS100P_11
{struct TreeNode{TreeNode* left;TreeNode* right;};int max(int a, int b){ return a > b ? a : b; }int helper(TreeNode* root, int& depth)	//返回的是最大距离，depth为当前深度{if (root == NULL){depth = 0;return 0;	}int leftDepth, rightDepth;int maxDistanceLeft = helper(root->left,leftDepth);int maxDistanceRight = helper(root->right, rightDepth);depth = leftDepth > rightDepth ? leftDepth : rightDepth;	//当前最大深度depth+=1;return max(maxDistanceLeft, max(maxDistanceRight, leftDepth + rightDepth));}int maxDistance(TreeNode* root){int depth;return helper(root, depth);}
}

这篇关于第十一题（求二叉树中节点的最大距离）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---