算法分析

• 从根结点1开始，往左右孩子做bfs遍历，队列存储的是某一层的所有节点，若当前层的总值比maxv大，则更新level

时间复杂度 $O(n)$

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int N = 100010;
    static int[] a = new int[N];
    static int n;
    static int bfs()
    {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(1);
        long maxv = Integer.MIN_VALUE;
        int level = 0;//答案的深度
        int levelNo = 0;//当前的深度
        while(!q.isEmpty())
        {
            levelNo ++;
            long res = 0;
            int len = q.size();
            for(int i = 0;i < len;i++)
            {
                int t = q.poll();
                res += a[t];
                if((t << 1 )<= n) q.add(t << 1);
                if((t << 1 | 1 )<= n) q.add(t << 1 | 1);
            }
            if(res > maxv)
            {
                maxv = res;
                level = levelNo; 
            }
        }
        return level;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(reader.readLine().trim());
        String[] s1 = reader.readLine().split(" ");
        for(int i = 1;i <= n;i++)
        {
            a[i] = Integer.parseInt(s1[i - 1]);
        }
        System.out.println(bfs());
    }
}