543. Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:Given a binary tree 

1 / \ 2 3 / \ 4 5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

思路：从根节点开始进行后序遍历，diameterCore(TreeNode* root)返回的是以该节点为根节点的子树的最长的一条路径，当该节点的父节点在计算以自己为根节点的最长直径时需要用到这个返回值，同时我还要计算在这棵子树中的最长直径，因此需要一个int maxlength值记录下每一棵子树中的最长直径，而最终返回的也是这个maxlength。

需要注意审题，题目里说了两个节点之间的算一条路径，而程序里面我们返回的是节点数，所以最后是maxlength-1。

class Solution {public: int diameterOfBinaryTree(TreeNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 0; int res = diameterCore(root); return maxlength - 1; } int diameterCore(TreeNode* root) { int maxright = 0, maxleft = 0; if (root->left == NULL && root->right == NULL) return 1; if (root->left != NULL) maxleft = diameterCore(root->left); if (root->right != NULL) maxright = diameterCore(root->right); int leng = maxright + maxleft + 1; if (leng > maxlength) maxlength = leng; if (maxleft > maxright) return maxleft + 1; else return maxright + 1; } int maxlength = 0;};