【递归3】完全二叉树的最大路径和

前言

• 树以及二叉树的概念
• 完全二叉树

1.树以及二叉树的概念:

在算法和数据结构中，树和二叉树是非常重要的概念，下面我会简单介绍一下它们的基本概念。

题目描述：

给定一个数组表示一颗完全二叉树的节点值，其中数组下标 $i$ 对应的节点值为 $arr[i]$，左子节点的下标为 $2i + 1$，右子节点的下标为 $2i + 2$。你需要求出所有从根节点到叶子节点路径的最大路径和。

路径的定义是从根节点到任意叶子节点的路径，每个节点的值加上当前节点的值。

请你实现一个递归算法来计算所有路径中的最大路径和。

输入

• 输入的第一行是一个整数 $n$ ($1 \leq n \leq 10^5$)，表示数组 $arr$ 的长度。
• 第二行是 $n$ 个整数 $arr_0, arr_1, ..., arr_{n-1}$ ($1 \leq arr[i] \leq 10^5$)，表示完全二叉树的节点值。

输出

• 输出一个整数，表示所有路径中的最大路径和。

样例

输入

5
1 2 3 4 5

输出

8

说明

• 数组表示的完全二叉树如下：

       1
     /   \
    2     3
   / \
  4   5

• 所有路径如下：
  • 从根节点到叶子节点的路径和分别是：
    • 路径 $1 \to 2 \to 4$，和为 $1 + 2 + 4 = 7$
    • 路径 $1 \to 2 \to 5$，和为 $1 + 2 + 5 = 8$
    • 路径 $1 \to 3$，和为 $1 + 3 = 4$
  • 所有路径中的最大路径和是 $8$。