JS求二叉树直径问题(编程实现获取二叉树的宽度)
正题
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 : 给定二叉树
1 / \ 2 3 / \ 4 5 复制代码
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
解析：二叉树的直径问题，实际上就是求二叉树深度问题的衍生问题。示例的二叉树深度是3，直径是 4-2-1-3 组成的长度，为3，但是深度并不等于直径长度，深度只是第一个节点到 Left 或 Right 节点最长的距离，而直径包含了这个距离，并且会包含另一侧的距离，是左右距离之和。
那么为为什么会提到 这条路径可能穿过也可能不穿过根结点呢，难道最长直径有可能会不经过根结点吗？答案是肯定的，如图
1 / \ 2 3 / \ 4 5 / \ 8 6 / \ 9 7 复制代码
如上图，最长直径为 [9-8-4-2-5-6-7] 组成的长度，为6，很显然没有穿过根节点。
那么如何去寻找最长直径呢？
实际上寻找最长直径的问题，就转化为，求节点左右深度之和最大为多少的问题。
首先要知道如何去求某个节点的最长深度，可参阅之前文章 计算二叉树深度.
求二叉树某节点最大深度代码：
var getNodeHeight = function (root) {
if (root === null) return 0
return Math.max(getNodeHeight(root.left), getNodeHeight(root.right)) + 1
}复制代码那么到某个节点的最长直径可以表示为:
let rootLength = getNodeHeight(root.left) + getNodeHeight(root.right)
继而采用递归的方式即可求解:
完整代码：
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))
}复制代码涉及到递归的问题就比较难以理解，还需多多累计经验和多思考才能抓住递归要点，从而获得正解！
作者：欧浪浪
链接：https://juejin.cn/post/7032310527464308772