树的最长路径|博客系列
# 树的最长路径
# 题目描述
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例：
给定二叉树
1
/ \
2 3
/ \
4 5
@前端进阶之旅: 代码已经复制到剪贴板
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 注意：两结点之间的路径长度是以它们之间边的数目表示。
# 解题思路
# coding
class Node {
constructor (value, left = null, right = null) {
this.value = value;
this.left = left;
this.right = right;
}
}
function maxDepth (node) {
if (!node) return 0;
return Math.max(maxDepth(node.left), maxDepth(node.right)) + 1;
}
function diameterOfBinaryTree (node) {
if (!node) return 0;
let max = 0;
let maxDepth = function (node) {
if (!node) return 0;
let left = maxDepth(node.left);
let right = maxDepth(node.right);
max = Math.max(left + right, max);
return Math.max(left, right) + 1;
}
maxDepth(node);
return max;
}
@前端进阶之旅: 代码已经复制到剪贴板
验证：
let tree = new Node(
-9,
new Node(
-5,
new Node(
9,
new Node(
6,
new Node(
0,
null,
new Node(-9)
),
new Node(6)
)
),
new Node(
-7,
null,
new Node(
-9,
null,
new Node(-9)
)
)
),
new Node(-9)
)
console.log(diameterOfBinaryTree(tree)) // 7
@前端进阶之旅: 代码已经复制到剪贴板
