543. Diameter of Binary Tree

题干简述：

求解一个二叉树的最大直径。

直径：该树两节点之间路径长度。这里的路径可以不经过根结点。

解题思路

这一题，看似有点麻烦，其实它的本质还是很简单的，也就是二叉树结点的高度求解。为什么它的本质是二叉树的高度求解呢？我们可以一点一点的来推导。

算法的求解其实就是数学问题的求解，所谓的推导，也就是一步步的寻找并发现规律。这里，我们不要一开始就从根结点 root 开始推导，那会有很多种情况，越推越复杂。

image20210709153329748.png

如图所示，一个二叉树，从其叶子结点开始倒推，基础只会有4种，分别是单个结点（无子树），仅有一个子树，拥有左右子树；对比他们的直径和高度，我们可以初步总结出一个规律，一个结点的最大直径 = 左右子树最大高度之和。所有的二叉树，都是由以上几种结点组成，这个结论同样适用。

在得出上述公式之后，我们要做的事情就跃然于纸上了，计算结点的最大高度。如何计算高度，欢迎去看我的另一篇题解 110. Balanced Binary Tree，这里我们需要做的额外处理是对比结点的左右子树高度，返回其中最大值。在计算高度的过程中，我们也需要同步去更新我们的最终结果，这样才能保证在递归的过程中，确保最终结果是正确的。

题解

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function(root) {
    let max = 0;

    const getDepth = (node) => {
      if (!node) return 0;
      const leftDepth = getDepth(node.left);
      const rightDepth = getDepth(node.right);
      max = Math.max(max, leftDepth + rightDepth);
      return Math.max(leftDepth, rightDepth) + 1;
    };
    getDepth(root);
    return max;
};

Q.E.D.

Take it easy