543. 二叉树的直径

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 //二叉树的直径只有两种情况：经过根节点和不经过根节点
11 class Solution 
12 {
13 public:
14     int diameterOfBinaryTree(TreeNode* root) 
15     {
16         if(root == NULL || root->left == 0 && root->right == 0) return 0;
17         int a = depth(root->left) != 0 ? depth(root->left) - 1 : 0;//看是否有左子树
18         int b = depth(root->right) != 0 ? depth(root->right) - 1: 0;//看是否有右子树
19 
20         if(root->left == 0 && root->right != 0) return b + 1;//只有右子树，一定会经过根节点
21         else if(root->left != 0 && root->right == 0) return a + 1;//只有左子树，一定会经过根节点
22         else return max(a + b + 2,max(diameterOfBinaryTree(root->left),diameterOfBinaryTree(root->right)));//经过根节点与不经过根节点求最大值
23         //a + b + 2——>经过根节点
24         //max(diameterOfBinaryTree(root->left),diameterOfBinaryTree(root->right))——>不经过根节点
25     }
26 
27     int depth(TreeNode* root)//求二叉树的深度
28     {
29         if(root == NULL) return 0;
30         if(root->left == 0 && root->right == 0) return 1;
31         return max(depth(root->left),depth(root->right)) + 1;
32     }
33 };