题目描述补充

题目：树上最长路径

给定一棵无向树（无环连通图），树中的节点由整数编号，节点之间通过边相连。请找出这棵树中任意两个节点之间的最长路径长度。这里的路径长度定义为路径上边的数量。

示例

考虑以下树：

    1
   / \
  2   3
 / \
4   5

最长路径是从节点4到节点5，长度为2（通过边2-4和边2-5）。

解题思路

1. 选择起点：从任意节点开始深度优先搜索（DFS）。
2. 更新信息：对于每个节点，我们需要记录从该节点出发的最长路径和次长路径（因为我们不能沿着最长路径的同一方向继续）。
3. 全局记录：在DFS过程中，我们需要记录并更新全局最长路径的长度。
4. 回溯更新：在回溯时，利用子节点的最长和次长路径信息来更新父节点的最长和次长路径。

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 示例代码

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 示例代码

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

码小课网站中有更多相关内容分享给大家学习，希望这些示例能帮助你理解和解决问题。