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.

解題思路

本題要求最長路徑長，可以轉化為求最長路徑中的節(jié)點個數(shù)-1
最長路徑包含以下三種情況：

1 根節(jié)點包含在最長路徑中，則節(jié)點個數(shù) = 左樹高 + 右樹高 + 1
2 最長路徑在左子樹中，則可以求左子樹的最長路徑的節(jié)點數(shù)目
3 最長路徑在右子樹中，則可以求右子樹的最長路徑的節(jié)點數(shù)目

對這三種情況進行比較，即可求出最長路徑

代碼

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        return numOfNode(root) - 1;
    }
    
    int numOfNode(TreeNode* root) {
        if (root == NULL) {
            return 0;
        } 
        //根節(jié)點包含在最長路徑中
        int ans = 1 + height(root->left) + height(root->right); 
        //最長路徑在左子樹中
        ans = max(ans, numOfNode(root->left));
        //最長路徑在右子樹中
        ans = max(ans, numOfNode(root->right));
        return ans;
    }
    
    int height(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        int l = 1, r = 1;
        if (root->left != NULL) {
            l += height(root->left);
        }
        if (root->right != NULL) {
            r += height(root->right);
        }
        return max(l, r);
    }
};

我們可以看到，在每一次計算根節(jié)點包含在最長路徑中的情況時，都要求一遍樹高。而求樹高是用遞歸實現(xiàn)的。在平衡二叉樹的情況下，T(n) = 2 * T(n/2) + O(n),時間復雜度為O(nlogn)。在樹退化為鏈的情況下，時間復雜度更是達到了O(n^2)

那么，有沒有辦法在線性時間內求解呢？

通過觀察，我們發(fā)現(xiàn)，在求最長路徑時，每一次數(shù)值的計算都用到了樹高。換而言之，每求得一次左右子樹樹高我們就計算一次包含該根節(jié)點的最長路徑，這樣，遍歷完整棵樹時，我們也就得到了整棵樹的最長路徑。

class Solution {
public:
    int ans = 1;
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        height(root);
        return ans - 1;
    }
    
    int height(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        int l = 1, r = 1;
        if (root->left != NULL) {
            l += height(root->left);
        }
        if (root->right != NULL) {
            r += height(root->right);
        }
        //原式為左子樹高+右子樹高+1，此處算了兩次根節(jié)點，故-1
        ans = max(ans, l + r - 1);
        return max(l, r);
    }
};