“This is the 11th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”
[B] [C] [D]
Given a binary tree, you need to calculate its diameter. The diameter length of a binary tree is the maximum of the path length of any two nodes. This path may or may not go through the root.
Example: Given a binary tree
1
/ \
2 3
/ \
4 5
Copy the code
Return 3, whose length is path [4,2,1,3] or [5,2,1,3].
Note: The length of the path between two nodes is expressed as the number of edges between them.
The solution is as follows:
The length of the path is the number of edges, because the path between two points must have one vertex, which is their common ancestor node
Therefore, we can obtain the path of each node as a vertex, as shown in the following figure:
The red number in the figure above is the path length of each node as a vertex, and the maximum path length of all nodes is the maximum path length of the binary tree
The code is as follows:
var diameterOfBinaryTree = function(root) { let res = 0; Function getHeight(root){if(root === null) return 0; const l = getHeight(root.left), Res = math.max (res,l+r) // Return math.max (l,r)+1} getHeight(root); return res; };Copy the code
We have now completed the diameter of leetcode-543-binary tree
If you have any questions or suggestions, please leave a comment!