解题思路

核心思路采用深度优先搜索（DFS）结合动态规划求解。对于树上的每个节点，定义两种状态：选择该节点或不选择该节点。通过递归计算子树的状态，自底向上得到最优解。

具体实现方法如下。对每个节点维护两个值：不选该节点时的最大亮度和选该节点时的最大亮度。状态转移关系为：若选择当前节点，则其左右子节点都不能选，亮度为当前值加上左右子树不选状态的亮度；若不选当前节点，则左右子节点可选可不选，取其最大值之和。最终答案为根节点两种状态的最大值。

由于输入采用层序遍历数组表示二叉树，可以直接在数组上进行 $DFS$ ，利用索引关系访问父子节点。对于索引为i的节点，其左子节点索引为 $2i+1$ ，右子节点索引为 $2i+2$ 。当索引超出范围或节点值为 $0$ 时，表示该位置无节点。

复杂度分析

1000ms

Difficulty: 5

所属公司 : 华为

算法与标签>动态规划

给定一个普通二叉树 bulbs , 我们在二叉树的节点上安装灯泡，每个灯泡都有自己的亮度值和开关，如果选择打开一个灯泡，则它相邻的父节点和子节点上的灯泡都不能被打开，计算能够获得的最大亮度总和。

假设 $bulbs[$ $]$ 是使用层序遍历存储的二叉树，其元素数值代表该对应树节点上灯泡的亮度值。

第一行输入为一个整数 $n$ ，代表 $bulbs[$ $]$ 的数组大小;

第二行输入为 $n$ 个整数，代表 $bulbs[$ $]$ 的元素值。

关于层序遍历的说明：

简单来说就是从根节点开始，一层一层从上到下、从左到右逐层遍历二叉树的节点，并按顺序将遍历结果保存在一维数组中。这样，我们可以得到一个包含二叉树所有节点灯泡亮度值的一维数组，顺序就是层序遍历的顺序。如果某个位置没有节点，用 $0$ 来占位，代表该处没有节点，亮度是 $0$ 。

参数取值范围：

一个整数，能够获得的最大亮度总和。

输入

5
1 2 3 0 4

输出

说明

1.	$[1, 2, 3,0,4]$ 代表输入的二叉树为:
2.	1
3.	/ \
4.	2 3
5.	\
6.	4
7.	打开根节点的右子节点和最下方的节点的灯泡,可以获得满足要求的最大亮度值 $3+4=7$ ，则返回 $7$

输入

5
1 2 0 0 4

输出

说明

1.	$[1, 2, 0,0,4]$ 代表输入的二叉树为:
2.	1
3.	/
4.	2
5.	\
6.	4
7.	打开根节点和最下方的节点的灯泡，可以获得满足要求的最大亮度值 $1+4=5$ ，则返回 $5$

输入

预期输出（选填）