P3904. 悄悄话花费的时间

解题思路

输入使用堆式下标表示二叉树：下标 i 的左右孩子分别位于 2i+1 和 2i+2，-1 表示空节点。定义递归函数返回“当前节点到某个叶节点的最大路径和”。空节点返回无结果；叶节点返回自身值；只有一个有效孩子时必须选择该孩子，两个孩子都有效时选择返回值较大者，再加当前节点值。

递归按定义比较当前节点到所有有效叶子的路径，不会把空孩子当成数值 0，因此即使节点值允许为负也能选到真实叶子。每个有效下标至多访问一次，时间 O(n)；堆式下标每深入一层至少翻倍，递归深度 O(log n)，输入数组占 O(n)。题目保证根节点存在。