题目

题目来源：力扣（LeetCode）

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

  1.       1<br />         / \<br />        2   3<br />       / \     <br />      4   5    <br />返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

思路分析

一条路径的长度为该路径经过的节点数减一，所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一。

对于某节点的左儿子向下遍历经过最多的节点数 L (即以左儿子为根的子树的深度) 和其右儿子向下遍历经过最多的节点数 R (即以右儿子为根的子树的深度) ，那么以该节点为起点的路径经过节点数的最大值即为 L+R+1 。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {number}
  12.  */
  13. var diameterOfBinaryTree = function (root) {
  14.   // 默认为1 是因为默认根节点自身的路径长度
  15.   let ans = 1;
  16.   function depth(rootNode) {
  17.     if (!rootNode) {
  18.       // 因为不存在根节点，所以深度即是0
  19.       return 0;
  20.     }
  22.     let L = depth(rootNode.left);
  23.     let R = depth(rootNode.right);
  24.     // 获取树的最长路径
  25.     // L + R + 1 = 左子树深度（节点个数） + 右子树深度（节点个数） + 1个根节点；
  26.     ans = Math.max(ans, L + R + 1);
  27.     // 已经知道因为根节点的左右子树的深度，则左右子树深度的最大值+1，即是以根节点为主的最大深度
  28.     return Math.max(L, R) + 1;
  29.   }
  30.   depth(root);
  31.   // 由于depth函数中已经默认加上自身跟节点路径，所以最后减去1
  32.   return ans - 1;
  33. };