解题思路

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

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

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

复杂度分析

时间复杂度为$O(n)$，其中$n$为节点数量。每个节点只会被访问一次，在访问过程中进行常数时间的状态转移计算。

空间复杂度为$O(h)$，其中$h$为树的高度。递归调用栈的深度取决于树的高度，最坏情况下为$O(n)$（退化为链表），平均情况下为$O(log n)$（平衡二叉树）。

代码实现

Python

def maxBrightness(bulbs):
    # DFS返回[不选当前节点的最大值, 选当前节点的最大值]
    def dfs(idx):
        # 越界或值为0表示无节点
        if idx>=n or bulbs[idx]==0:
            return [0,0]
        # 递归计算左右子树
        left=dfs(2*idx+1)
        right=dfs(2*idx+2)
        # 不选当前节点:子节点可选可不选
        not_select=max(left)+max(right)
        # 选当前节点:子节点都不能选
        select=bulbs[idx]+left[0]+right[0]
        return [not_select,select]
    n=len(bulbs)
    result=dfs(0)
    return max(result)

n=int(input())
bulbs=list(map(int,input().split()))
print(maxBrightness(bulbs))

Java

import java.util.*;

public class Main{
    static int[] dfs(int idx,int[] bulbs,int n){
        // 越界或值为0表示无节点
        if(idx>=n||bulbs[idx]==0){
            return new int[]{0,0};
        }
        // 递归计算左右子树
        int[] left=dfs(2*idx+1,bulbs,n);
        int[] right=dfs(2*idx+2,bulbs,n);
        // 不选当前节点:子节点可选可不选
        int notSelect=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        // 选当前节点:子节点都不能选
        int select=bulbs[idx]+left[0]+right[0];
        return new int[]{notSelect,select};
    }
    
    static int maxBrightness(int[] bulbs){
        int[] result=dfs(0,bulbs,bulbs.length);
        return Math.max(result[0],result[1]);
    }
    
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] bulbs=new int[n];
        for(int i=0;i<n;i++){
            bulbs[i]=sc.nextInt();
        }
        System.out.println(maxBrightness(bulbs));
    }
}

C++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// DFS返回pair<不选当前节点的最大值,选当前节点的最大值>
pair<int,int> dfs(int idx,vector<int>& bulbs,int n){
    // 越界或值为0表示无节点
    if(idx>=n||bulbs[idx]==0){
        return {0,0};
    }
    // 递归计算左右子树
    auto left=dfs(2*idx+1,bulbs,n);
    auto right=dfs(2*idx+2,bulbs,n);
    // 不选当前节点:子节点可选可不选
    int notSelect=max(left.first,left.second)+max(right.first,right.second);
    // 选当前节点:子节点都不能选
    int select=bulbs[idx]+left.first+right.first;
    return {notSelect,select};
}

int maxBrightness(vector<int>& bulbs){
    auto result=dfs(0,bulbs,bulbs.size());
    return max(result.first,result.second);
}

int main(){
    int n;
    cin>>n;
    vector<int> bulbs(n);
    for(int i=0;i<n;i++){
        cin>>bulbs[i];
    }
    cout<<maxBrightness(bulbs)<<endl;
    return 0;
}

题目内容

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

输入描述

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

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

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

关于层序遍历的说明：

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

参数取值范围：

• $1 <= bulbs.length<=10^6$

• $0 <= bulbs[i]<= 100$

输出描述

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

样例1

输入

5
1 2 3 0 4

输出

7

说明

样例2

输入

5
1 2 0 0 4

输出

5

说明