首页 > 代码库 > 算法题——二叉树中结点的最远距离
算法题——二叉树中结点的最远距离
题目：给定一棵二叉树，结点的距离就是两个结点之间路径包含的结点的数目，求结点的最大距离。
可以参考这两篇文章：《编程之美: 求二叉树中节点的最大距离》的另一个解法 和 Tree Diameter
思路：
在每一个结点处，求两个信息：以该结点为根的树的高度，以及以该结点为根的树中包含的最大距离。
因为所求的最大距离，如果是跨越根结点的，则为两个子树的树高度之和+1，如果是不跨越根结点的，则为左右子树中的最大距离的最大值。
代码：
①参考第一篇文章，每次返回两个值：
1 struct TreeNode 2 { 3 int val; 4 TreeNode *left, *right; 5 }; 6 7 //每次返回两个值 8 struct RetVal 9 {10 int height;11 int max_dist;12 RetVal(int h, int d): height(h), max_dist(d)13 {14 }15 };16 17 RetVal maxDistInTree(TreeNode *root)18 {19 if(root == NULL)20 return RetVal(0, 0);21 22 RetVal lcr = maxDistInTree(root->left); //left child result23 RetVal rcr = maxDistInTree(root->right);24 25 RetVal result;26 result.height = 1 + max(lcr.height, rcr.height);27 result.max_dist = max( max(lcr.max_dist, rcr.max_dist), lcr.height + rcr.height + 1 );28 29 return result;30 }
②参考第二篇文章，分别求高度和树直径
1 //单独求高度和直径(最大距离) 2 int treeHeight(TreeNode *root) 3 { 4 if(root == NULL) 5 { 6 return 0; 7 } 8 else 9 {10 return 1 + max( treeHeight(root->left), treeHeight(root->right) );11 }12 }13 14 int treeDiam(TreeNode *root)15 {16 if(root == NULL)17 return 0;18 19 int l_height = treeHeight(root->left);20 int r_height = treeHeight(root->right);21 22 int l_diam = treeDiam(root->left);23 int r_diam = treeDiam(root->right);24 25 return max( max(l_diam, r_diam),26 l_height + r_height + 1);27 }
算法题——二叉树中结点的最远距离
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。