P3904. 悄悄话花费的时间

解题思路

分两步完成题目。首先根据所给定的数组还原二叉树，再进行 DFS 找到从根节点到叶节点和最大的路径。 建树有两种写法，寻找最大路径也有两种写法。故本题至少有四种解法，大家可以自行选择。

构建二叉树

首先需要明确题目所给定的数组是如何表示一棵二叉树的。以示例 0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2 为例，把其中的空节点在树状结构中补全可以得到。

容易发现，输入数组类似于二叉树的 层序遍历结果，但把空节点也一并输出。 如果标注出节点在原数组中的下标，可以看到。

容易观察出规律：**如果某一个节点在数组下标为 i，那么其左孩子和右孩子（如果存在，不为 -1）在数组中的下标分别为 i*2+1 和 i*2+2。 基于这个规律，可以很容易地使用 递归 或者 迭代** 的方式还原出二叉树。其中递归方法效率更高也更简洁，但是迭代方法对于初学者更加友好，大家可以自由选择。

迭代写法

递归写法

寻找最大路径

还原出二叉树之后，剩下的工作就是寻找从根节点到叶节点的 最大和路径。显然应该使用 DFS 来实现。存在 自底向上 和 自顶向下 两种不同写法。

自顶向下 DFS

自顶向下方法类似于 回溯，从上往下记录路径和。考虑递归三要素。

• 递归终止条件：遇到叶节点，更新全局答案变量。
• 递归子问题：把当前节点 node 的值 node.val 计入路径和中；如果左节点或右节点不为空，递归地考虑左节点和右节点。
• 递归入口：从根节点 root 开始递归，初始时路径和 path_sum 为 0。

自底向上 DFS

自底向上方法的核心在于 优先计算以子节点为根节点的最大路径和，并把结果回传，从下往上计算路径和。考虑递归三要素。

• 递归终止条件：遇到空节点，返回 0。表示此时空节点对路径和没有贡献。
• 递归子问题：递归函数 dfs(node) 的返回值表示，当以 node 作为根节点时，node 到其下方的叶节点的最大路径和。考虑 node 的左节点和右节点递归调用的结果 dfs(node.left) 和 dfs(node.right)，其中的较大值应该被考虑进以 node 作为根节点的最大路径和。把当前节点 node 的值 node.val 计入当前路径和 path_sum 中，将当前最大路径和 path_sum 传回上一层递归。
• 递归入口：从根节点 root 开始递归。

这也是一种 树形 DP 思想的体现。

代码

解法一：迭代写法建树 + 自顶向下 DFS

复杂度分析 设 n 为输入数组的长度（包含用 -1 表示的空节点占位）。建树阶段：迭代写法先扫一遍数组为每个非 -1 位置建节点，再扫一遍利用「下标 i 的左右孩子在 i*2+1 和 i*2+2」的规律连接指针，两轮都是 O(n)；递归写法对每个下标至多访问一次，同样是 O(n)。求最大路径阶段：无论自顶向下（回溯式累加路径和）还是自底向上（子树最大路径和回传）的 DFS，每个真实节点都只被访问一次，每次访问做常数量的比较与加法，也是 O(n)。因此整体时间复杂度为 O(n)，瓶颈只是对数组和树各扫一遍。空间上，node_lst（或递归建树产生的节点）占 O(n)；DFS 递归栈的深度等于树高 h，由于输入按满二叉树下标编号，h 为 O(log n)，但最坏（数组大量为 -1 退化成链）可达 O(n)，故总空间 O(n)。