#P4225. 第3题-最亮二叉树
-
1000ms
Tried: 121
Accepted: 36
Difficulty: 5
所属公司 :
华为
时间 :2025年10月15日-非AI方向(通软&嵌软&测试&算法&数据科学)
-
算法标签>动态规划
第3题-最亮二叉树
解题思路
核心思路采用深度优先搜索(DFS)结合动态规划求解。对于树上的每个节点,定义两种状态:选择该节点或不选择该节点。通过递归计算子树的状态,自底向上得到最优解。
具体实现方法如下。对每个节点维护两个值:不选该节点时的最大亮度和选该节点时的最大亮度。状态转移关系为:若选择当前节点,则其左右子节点都不能选,亮度为当前值加上左右子树不选状态的亮度;若不选当前节点,则左右子节点可选可不选,取其最大值之和。最终答案为根节点两种状态的最大值。
由于输入采用层序遍历数组表示二叉树,可以直接在数组上进行DFS,利用索引关系访问父子节点。对于索引为i的节点,其左子节点索引为2i+1,右子节点索引为2i+2。当索引超出范围或节点值为0时,表示该位置无节点。
复杂度分析
时间复杂度为O(n),其中n为节点数量。每个节点只会被访问一次,在访问过程中进行常数时间的状态转移计算。
空间复杂度为O(h),其中h为树的高度。递归调用栈的深度取决于树的高度,最坏情况下为O(n)(退化为链表),平均情况下为O(logn)(平衡二叉树)。
代码实现
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<=106
-
0<=bulbs[i]<=100
输出描述
一个整数,能够获得的最大亮度总和。
样例1
输入
5
1 2 3 0 4
输出
7
说明
| 1. | [1,2,3,0,4] 代表输入的二叉树为: |
|---|---|
| 2. | 1 |
| 3. | / \ |
| 4. | 2 3 |
| 5. | \ |
| 6. | 4 |
| 7. | 打开根节点的右子节点和最下方的节点的灯泡,可以获得满足要求的最大亮度值 3+4=7,则返回 7 |
样例2
输入
5
1 2 0 0 4
输出
5
说明
| 1. | [1,2,0,0,4] 代表输入的二叉树为: |
|---|---|
| 2. | 1 |
| 3. | / |
| 4. | 2 |
| 5. | \ |
| 6. | 4 |
| 7. | 打开根节点和最下方的节点的灯泡,可以获得满足要求的最大亮度值 1+4=5,则返回 5 |