The topic of dry

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.

Source: LeetCode link: leetcode-cn.com/problems/di… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution: Depth-first search

The fundamental reason for this problem is to find the maximum length of a two-node path. Since any structure can be viewed as starting from the same root node, the sum of the depths of the left and right nodes starting from this root node is essentially what we’re looking for.

Tell we can start from the root node in the body, also can not start from the root node, if must go through the root node that we only need to add those trees around the sum when the recursive, but weight told we don’t need, then we can set a maximum value, each time when met is greater than the current maximum element directly record.

It looks like this:

Code implementation:

 / * * *@param {TreeNode} root
  * @return {number}* /
 var diameterOfBinaryTree = function (root) {
     var Max = 0;
     function doFind(root) {
         if (root == null) return 0;
         let num1 = doFind(root.left);
         let num2 = doFind(root.right);
         Max = Math.max(num2 + num1, Max)
         return Math.max(num1, num2) + 1
     }
     doFind(root);
     return Max;
 };
Copy the code

\