Skip to main content

543. Diameter of Binary Tree

分析

第一种方法 diameterOfBinaryTree 递归调用
结合三种信息求最值
因为多次用给了 getDepth getDepth 注意进行 cache

第二种方法 在后续遍历的时候就可以直接拿到
只用过了一次 getDepth 不用cache

题解

function diameterOfBinaryTree(root: TreeNode | null): number {
if (!root) {
return 0
}

const memoGetDepth = new Map<TreeNode, number>()

const getDepth = (root: TreeNode | null): number => {
if (!root) {
return 0
}
if (memoGetDepth.get(root) !== undefined) {
return memoGetDepth.get(root)
}

const res = Math.max(
getDepth(root.left),
getDepth(root.right)
) + 1

memoGetDepth.set(root, res)

return res
}

return Math.max(
// 获得左右深度,求和.
getDepth(root.left) + getDepth(root.right),
diameterOfBinaryTree(root.left),
diameterOfBinaryTree(root.right)
)
};
function diameterOfBinaryTree(root: TreeNode | null): number {
let ans = 0

const getDepth = (root: TreeNode | null): number => {
if (!root) {
return 0
}

const leftDepth = getDepth(root.left)
const rightDepth = getDepth(root.right)
ans = Math.max(ans, leftDepth + rightDepth)

return 1 + Math.max(leftDepth, rightDepth)
}

getDepth(root)

return ans
};