求二叉樹(shù)的直徑申尤，深度優(yōu)先遍歷癌幕。
- 時(shí)間復(fù)雜度O(N)，為遍歷一棵二叉樹(shù)的時(shí)間復(fù)雜度昧穿，每個(gè)節(jié)點(diǎn)只被訪問(wèn)一次勺远。
- 空間復(fù)雜度O(H)，H為二叉樹(shù)的高度时鸵，遞歸函數(shù)在遞歸過(guò)程中需要為每一層遞歸函數(shù)分配椊悍辏空間厅瞎，這里需要額外的空間且取決于遞歸的深度。每次遞歸調(diào)用的函數(shù)里只用了常數(shù)個(gè)變量初坠。
- 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
}
