11、二叉树的直径

两个叶子节点之间的路径 = 根节点左右儿子的深度之和 ；

节点的深度是节点左右子树的节点深度+1---max(L,R),LR是左右节点深度;

一颗二叉树的直径长度是任意两个节点路径长度的最大值，可能这条路径不会穿过根节点。路径的长度为经过该路径的节点数减去1，所以求直径等效于求路径经过节点数的最大值减去1.

因为直径长度可能不会经过根节点，所以在程序开始的时候定义一个全局变量用来保存每一次计算路径的最大值，该路径-1就是最长直径长度。

int ans; //全局变量保存每次路径的最大值 int max(int a,int b){ return (a>=b ? a:b); } int deepth(struct TreeNode *rt){ //递归求路径长度 = L+R+1 if(rt == NULL) return 0; int L = deepth(rt->left); int R = deepth(rt->right); ans = max(ans,L+R+1); //保存最大路径 return max(L,R)+1; } int diameterOfBinaryTree(struct TreeNode* root){ ans = 1; deepth(root); return ans-1; }