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 /** 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 class Solution { 11 public: 12 int diameterOfBinaryTree(TreeNode* root) 13 { 14 res = 1; 15 treeDepth(root); 16 return res - 1; 17 } 18 int treeDepth(TreeNode* node) 19 { 20 if(node == nullptr) 21 return 0; 22 int L = treeDepth(node->left); 23 int R = treeDepth(node->right); 24 res = max(res,L+R+1); 25 return max(L,R)+1; 26 } 27 private: 28 int res; 29 };