I hope the future is promising
To the chase
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].
Analysis: the diameter of binary tree, in fact, is the derivation of the problem of the depth of binary tree. In the example, the depth of the binary tree is 3, and the diameter is the length composed of 4-2-1-3, which is 3. However, the depth is not equal to the diameter length. The depth is just the longest distance from the first node to the Left or Right node, while the diameter contains this distance and will include the distance on the other side, which is the sum of the Left and Right distances.
So why is it that this path may or may not go through the root, is it possible that the longest diameter may not go through the root? The answer is yes, as shown here
1
/ \
2 3
/ \
4 5
/ \
8 6
/ \
9 7
Copy the code
As shown in the figure above, the longest diameter [9-8-4-2-5-6-7] consists of a length of 6, which obviously does not pass through the root node.
So how do you find the maximum diameter?
In fact, the problem of finding the longest diameter is transformed into the problem of finding the maximum sum of the left and right depths of nodes.
First, you need to know how to find the maximum depth of a node. See the previous article calculating the depth of a binary tree.
To find the maximum depth code of a node in the binary tree:
var getNodeHeight = function (root) {
if (root === null) return 0
return Math.max(getNodeHeight(root.left), getNodeHeight(root.right)) + 1
}
Copy the code
Then the longest diameter to a node can be expressed as:
let rootLength = getNodeHeight(root.left) + getNodeHeight(root.right)
Then the solution can be solved by recursion:
Complete code:
var getNodeHeight = function (root) {
if (root === null) return 0
return Math.max(getNodeHeight(root.left), getNodeHeight(root.right)) + 1
}
var diameterOfBinaryTree = function(root) {
if (root === null) return 0
let rootLength = getNodeHeight(root.left) + getNodeHeight(root.right)
return Math.max(rootLength, diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right))
}
Copy the code
Problems involving recursion are more difficult to understand, but also need a lot of accumulated experience and thinking to grasp the points of recursion, so as to obtain the correct solution!