当前位置： 面试刷题>> 树上最长路径 (经典算法题500道)
### 题目描述补充
题目：**树上最长路径**
给定一棵无向树（无环连通图），树中的节点由整数编号，节点之间通过边相连。请找出这棵树中任意两个节点之间的最长路径长度。这里的路径长度定义为路径上边的数量。
### 示例
考虑以下树：
```
1
/ \
2 3
/ \
4 5
```
最长路径是从节点4到节点5，长度为2（通过边2-4和边2-5）。
### 解题思路
1. **选择起点**：从任意节点开始深度优先搜索（DFS）。
2. **更新信息**：对于每个节点，我们需要记录从该节点出发的最长路径和次长路径（因为我们不能沿着最长路径的同一方向继续）。
3. **全局记录**：在DFS过程中，我们需要记录并更新全局最长路径的长度。
4. **回溯更新**：在回溯时，利用子节点的最长和次长路径信息来更新父节点的最长和次长路径。
### PHP 示例代码
```php
class TreeNode {
public $val;
public $children = [];
function __construct($val = 0) {
$this->val = $val;
}
}
function dfs($node, &$longest, &$pathLengths) {
if (!$node) return [0, 0]; // 返回当前节点的最长和次长路径长度
$max1 = $max2 = 0;
foreach ($node->children as $child) {
list($childMax1, $childMax2) = dfs($child, $longest, $pathLengths);
if ($childMax1 > $max1) {
$max2 = $max1;
$max1 = $childMax1;
} elseif ($childMax1 > $max2) {
$max2 = $childMax1;
}
}
$pathLengths[$node->val] = $max1 + 1; // 存储到该节点的最长路径长度
$longest = max($longest, $max1 + $max2); // 更新全局最长路径
return [$max1 + 1, max($max2 + 1, 0)]; // 返回当前节点的最长和次长路径长度+1（考虑当前边）
}
function findLongestPath($root) {
$longest = 0;
$pathLengths = [];
dfs($root, $longest, $pathLengths);
return $longest;
}
// 示例用法
$root = new TreeNode(1);
$root->children = [new TreeNode(2), new TreeNode(3)];
$root->children[0]->children = [new TreeNode(4), new TreeNode(5)];
echo findLongestPath($root); // 输出 2
```
### Python 示例代码
```python
class TreeNode:
def __init__(self, val=0, children=None):
self.val = val
self.children = children if children is not None else []
def dfs(node, longest, path_lengths):
if not node:
return 0, 0
max1, max2 = 0, 0
for child in node.children:
child_max1, child_max2 = dfs(child, longest, path_lengths)
if child_max1 > max1:
max1, max2 = child_max1, max1
elif child_max1 > max2:
max2 = child_max1
path_lengths[node.val] = max1 + 1
longest[0] = max(longest[0], max1 + max2)
return max1 + 1, max(max2 + 1, 0)
def findLongestPath(root):
longest = [0]
path_lengths = {}
dfs(root, longest, path_lengths)
return longest[0]
# 示例用法
root = TreeNode(1, [TreeNode(2, [TreeNode(4), TreeNode(5)]), TreeNode(3)])
print(findLongestPath(root)) # 输出 2
```
### JavaScript 示例代码
```javascript
class TreeNode {
constructor(val, children = []) {
this.val = val;
this.children = children;
}
}
function dfs(node, longest, pathLengths) {
if (!node) return [0, 0];
let max1 = 0, max2 = 0;
for (const child of node.children) {
const [childMax1, childMax2] = dfs(child, longest, pathLengths);
if (childMax1 > max1) {
[max2, max1] = [max1, childMax1];
} else if (childMax1 > max2) {
max2 = childMax1;
}
}
pathLengths[node.val] = max1 + 1;
longest[0] = Math.max(longest[0], max1 + max2);
return [max1 + 1, Math.max(max2 + 1, 0)];
}
function findLongestPath(root) {
const longest = [0];
const pathLengths = {};
dfs(root, longest, pathLengths);
return longest[0];
}
// 示例用法
const root = new TreeNode(1, [
new TreeNode(2, [
new TreeNode(4),
new TreeNode(5)
]),
new TreeNode(3)
]);
console.log(findLongestPath(root)); // 输出 2
```
**码小课网站中有更多相关内容分享给大家学习**，希望这些示例能帮助你理解和解决问题。