LeetCode 543. 二叉树的直径

• 题目：
  给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 :
给定二叉树

      1
     / \
    2   3
   / \     
  4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

• 解题思路
  方法一
  二叉树的直径为每一个节点左右深度之和的最大值。只用使用一个全局变量max，在求出深度度的同时，记录每一个节点左右深度之和的最大值。
  代码实现(C++)

 int sum = 0;
    int height(TreeNode* root)           //求出树的高度
    {
        if(!root)
            return 0;
        int a = height(root->left);
        int b = height(root->right);
        sum = max(sum, a + b);
        return a > b? a+1: b+1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        height(root);
        return sum;
    }

方法二：
二叉树的直径：二叉树中从一个结点到另一个节点最长的路径，叫做二叉树的直径
采用分治和递归的思想：根节点为root的二叉树的直径 = max(root-left的直径，root->right的直径，root->left的最大深度+root->right的最大深度+1)

代码实现：

int sum = 0;
    int height(TreeNode* root)           //求出树的高度
    {
        if(!root)
            return 0;
        int a = height(root->left);
        int b = height(root->right);
        sum = max(sum, a + b);
        return a > b? a+1: b+1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        if(!root)
            return 0;
        int l = diameterOfBinaryTree(root->left);             //左子树的直径
        int r = diameterOfBinaryTree(root->right);          //右子树的直径
        int hl = height(root->left);                       //左子树的深度
        int hr = height(root->right);                       //右子树的深度
        return max(max(l,r) ,hl + hr);
    }