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
最长路径包含以下三种情况：

1 根节点包含在最长路径中，则节点个数 = 左树高 + 右树高 + 1
2 最长路径在左子树中，则可以求左子树的最长路径的节点数目
3 最长路径在右子树中，则可以求右子树的最长路径的节点数目

对这三种情况进行比较，即可求出最长路径

代码

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;
        } 
        //根节点包含在最长路径中
        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);
    }
};

我们可以看到，在每一次计算根节点包含在最长路径中的情况时，都要求一遍树高。而求树高是用递归实现的。在平衡二叉树的情况下，T(n) = 2 * T(n/2) + O(n),时间复杂度为O(nlogn)。在树退化为链的情况下，时间复杂度更是达到了O(n^2)

那么，有没有办法在线性时间内求解呢？

通过观察，我们发现，在求最长路径时，每一次数值的计算都用到了树高。换而言之，每求得一次左右子树树高我们就计算一次包含该根节点的最长路径，这样，遍历完整棵树时，我们也就得到了整棵树的最长路径。

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，此处算了两次根节点，故-1
        ans = max(ans, l + r - 1);
        return max(l, r);
    }
};