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.

---

本题要求一棵树的直径，树的直径的定义是树中任意两点间的最长距离。
任意两点间的最长路径有如下三种选择：

1. 经过根节点的最长路径
2. 在左子树中不经过根节点的最长路径
3. 在右子树中不经过根节点的最长路径

其中第1种情况比较好处理，必须经过根节点，又必须是最长路径，则路径长度肯定是左右子树的最大高度之和+1(根节点)。第2、3种情况就更好处理了，就是以左右孩子为根递归计算最长路径。
代码如下：

class Solution {
private:
    int getHeight(TreeNode* root)
    {
        if (!root)
            return 0;
        int lh = getHeight(root->left);
        int rh = getHeight(root->right);
        return 1 + max(lh, rh);
    }

public:
    int diameterOfBinaryTree(TreeNode* root)
    {
        if (!root)
            return 0;
        //int ans = 1 + getHeight(root->left) + getHeight(root->right); // 节点数
        int ans = getHeight(root->left) + getHeight(root->right); // 路径数
        ans = max(ans, diameterOfBinaryTree(root->left));
        ans = max(ans, diameterOfBinaryTree(root->right));
        return ans;
    }
};

本代码提交AC，用时22MS。

参考：http://www.geeksforgeeks.org/diameter-of-a-binary-tree/，这篇博客的路径是指节点数，而本题的路径是指边数，所以第12行不能再加1了。

以上代码递归的过程是从根节点往孩子节点递归，这样计算高层节点的高度时，其实已经计算过低层节点的高度了，后面递归到低层节点时，会重复计算。所以代码还可以优化，比如可以不断递归到叶子节点再返回，这样高层节点的高度就可以直接用低层节点的高度加1计算得到，可以省不少时间。

二刷。在求解路径的同时可计算高度，而且先递归到叶子，然后不断从往上走，代码如下：

class Solution {
public:
	int DiameterAndHeight(TreeNode* root, int &height) {
		if (root == NULL || (root->left == NULL && root->right == NULL)) {
			height = 0;
			return 0;
		}
		int left_height = 0, right_height = 0;
		int left_diameter = DiameterAndHeight(root->left, left_height);
		int right_diameter = DiameterAndHeight(root->right, right_height);
		height = max(left_height, right_height) + 1;
		int left_edge = root->left == NULL ? 0 : 1, right_edge = root->right == NULL ? 0 : 1;
		return max(max(left_diameter, right_diameter), left_height + right_height + left_edge + right_edge);
	}
	int diameterOfBinaryTree(TreeNode* root) {
		int height = 0;
		return DiameterAndHeight(root, height);
	}
};

本代码提交AC，用时8MS，快了不少。