从二叉树的节点A出发，可以向上或者向下走，但沿途的节点只能经过一次，当到达节点B时，路径上的节点数叫作A到B的距离。对于给定的一棵二叉树，求整棵树上节点间的最大距离。
给定一个二叉树的头结点root，请返回最大距离。保证点数大于等于2小于等于500.
思路：修改后序遍历
对于给定的节点root，最远距离只可能来自以下三种情况： 1、左子树的最远距离 2、右子树的最远距离 3、左子树上距离root最远长度和右子树上距离root最远长度之和加1； 递归遍历即可。每个递归返回两个值，一个是距离root的最远距离，另一个是以root为头节点的树上最远距离，使用动态数组或者vector，不能直接返回数组指针，每个局部函数执行完内存就释放掉了。
计算结点root所在子树的最长距离，需要已知：左子树的最长距离left[0]，左子树的高度left[1]；右子树的最长距离right[0]，右子树的高度right[1]. 然后比较max(left[0],right[0],(left[1]+right[1]+1))，最大值就是这棵二叉树的最大距离，即对于每个子树，需要求出它的最大距离和最大高度。 可以使用递归来实现，求出这个根结点的最大距离a[0]和最大高度a[1]并返回这2个数值。其中a[0]= max(left[0],right[0],(left[1]+right[1]+1))； 而由于要返回这棵子树的高度，如何求子树的高度呢？二叉树的高度就是它的2个子树高度中的较大值再加上1，即a[1]=max(left[1], right[1])+1;
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class LongestDistance { public: int findLongest(TreeNode* root) { if(!root) return 0; vector<int> res=getDist(root);//调用递归函数来求得最大距离a[0]和高度a[1] return res[0]; } vector<int> getDist(TreeNode* root){ vector<int> a(2,0); if(!root) return a; vector<int> left=getDist(root->left);//左子树的结果 vector<int> right=getDist(root->right);//右子树的结果 a[1]=max(left[1],right[1])+1;//最远距离 a[0]=max(max(left[0],right[0]),left[1]+right[1]+1);//最远长度 return a; } };
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class LongestDistance { public: int findLongest(TreeNode* root) { int dist=0; getMaxDist(root,dist); return dist; } int getMaxDist(TreeNode* node,int& dist){ if(!node)return 0; int leftDist=getMaxDist(node->left,dist); int rightDist=getMaxDist(node->right,dist); dist=max(leftDist+rightDist+1,dist); return max(leftDist,rightDist)+1; } };
