题解 | #二叉树的直径#

简单的递归就可以解决

核心 是要明白递归的判断要素：以当前节点为头结点的树，直径就是左右两个子树的高度相加，故有三个情况

• 以 root 为头结点的树，最大直径就是左右两个子树的高度相加

• 左子树的直径是以 root->left 为头结点的树，最大直径同理

• 右子树的直径是以 root->right 为头结点的树，最大直径同理

最后，取三者最大值即可。

c++代码实现

class Solution {
public:
    // 求高度的函数
    int getHight(TreeNode* Node){
        if(!Node) return 0;
        int L=getHight(Node->left), R=getHight(Node->right);
        return L>R?L+1:R+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        // write code here
        if(!root) return 0;  //终止条件，为null则没直径，返回0
        int now_diamater = getHight(root->left) + getHight(root->right);  //当前节点的最大直径就是左右两子树的高度相加
        //当前节点，左子节点，右子节点 （为头）的树直径，取最大值
        return max({now_diamater, diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right)});
    }
};