寻找一棵树的直径

本文介绍了寻找一棵树的直径的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我已经编写了用于查找二叉树直径的代码.但是我无法弄清楚哪里出了问题.我编写的两个函数及其定义如下:-

I have written code for finding the diameter of binary tree. But I am unable to figure out where is it going wrong . The two functions that I have written and their definition are as follows :-

int btree::diameteroftree(node* leaf) { if (leaf==NULL) return 0; int lheight = hieghtoftree(leaf->left); int rheight = hieghtoftree(leaf->right); int ldiameter = diameteroftree(leaf->left); int rdiameter = diameteroftree(leaf->right); return max(lheight + rheight + 1,max(ldiameter,rdiameter)); } int btree::hieghtoftree(node* leaf) { int left=0,right=0; if(leaf==NULL) return -1; else { left=hieghtoftree(leaf->left); right=hieghtoftree(leaf->right); if(left > right) return left +1; else return right+1; } }

我无法弄清楚我在哪里出问题了.有人可以让我知道...

I am unable to figure out where am I going wrong here . Can someone let me know ...

推荐答案

您要返回最长路径上的节点数.因此，您算法中的问题是这一行:

You want to return the number of nodes on the longest path. Therefore, the problem in your algorithm is this line:

return max(lheight + rheight + 1,max(ldiameter,rdiameter));

其中

rootDiameter = lheight + rheight + 1

是从左侧树的最深节点到右侧树的最深节点的路径长度.但是，此计算是不正确的.单个节点返回的高度为0，因此不会被计算在内.您有两种选择:

is the length of the path from the deepest node of the left tree to the deepest node of the right tree. However, this calculation is not correct. A single node returns a height of 0, so it will not be counted. You have two options:

更改 hieghtoftree 以返回最深路径上的节点数，而不是跳数"

总结您的问题

Change hieghtoftree to return the number of nodes on the deepest path and not the number of "hops"

Address this problem in your summation

.

return max(lheight + rheight + 3,max(ldiameter,rdiameter));