543. Diameter of Binary Tree

求二叉树的直径，深度优先遍历。

• 时间复杂度O(N)，为遍历一棵二叉树的时间复杂度，每个节点只被访问一次。
• 空间复杂度O(H)，H为二叉树的高度，递归函数在递归过程中需要为每一层递归函数分配栈空间，这里需要额外的空间且取决于递归的深度。每次递归调用的函数里只用了常数个变量。
• Runtime: 88 ms, faster than 84.07%
• Memory Usage: 41.9 MB, less than 73.68%

/**
 * 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}
 */
let max = 0
var diameterOfBinaryTree = function(root) {
    dfs(root)
    return max
};

var dfs = function(root) {
    if(root === null) return 0
    let left = root.left !== null ? dfs(root.left) : 0
    let right = root.right !== null ? dfs(root.right) : 0
    let cur = left + right
    if (max < cur) max = cur
    return Math.max(left, right) + 1
}