题目描述：

给定一个数组表示一颗完全二叉树的节点值，其中数组下标 $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$。

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

前言

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

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

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

1. 树（Tree）

树是一种由节点（Node）组成的非线性数据结构，其中的每个节点可以有零个或多个子节点。树通常用来表示层次结构的数据关系，比如文件系统、家谱等。

• 根节点（Root）：树中的第一个节点，根节点没有父节点。
• 父节点（Parent）：一个节点的直接上级节点。
• 子节点（Child）：一个节点的直接下级节点。
• 叶子节点（Leaf）：没有任何子节点的节点。
• 深度（Depth）：从根节点到当前节点的路径长度。
• 高度（Height）：从当前节点到叶子节点的最长路径长度。
• 度（Degree）：节点的子节点数目。

树的常见类型有：

• 二叉树：每个节点最多有两个子节点。
• 平衡树：比如AVL树，二叉搜索树（BST）等，它们有一些特定的规则来保证树的平衡性。

2. 二叉树（Binary Tree）

二叉树是一种特殊的树结构，它的每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树是最常见的一种树结构，广泛应用于各种算法和数据结构中。

如图是一颗二叉树:

二叉树的性质：

• 每个节点最多有两个子节点。
• 每个节点有两个指针，一个指向左子节点，另一个指向右子节点。

二叉树的类型：

• 满二叉树：所有的非叶子节点都有两个子节点，且所有叶子节点都在同一层。
• 完全二叉树：除了最后一层外，其他每一层的节点都达到最大节点数，且最后一层的节点从左到右连续排列。
• 二叉搜索树（BST）：对于每一个节点，其左子树的所有节点值都小于该节点的值，右子树的所有节点值都大于该节点的值。
• 平衡二叉树（AVL树、红黑树）：为了保持高效的查询、插入和删除操作，这些树会自动保持平衡，即左右子树的高度差不超过某个阈值。

二叉树的遍历：

二叉树的遍历方式有多种，常见的有：

• 前序遍历（Pre-order）：访问根节点，再访问左子树，最后访问右子树。 如图: 这是树的前序遍历示意图，红色数字表示前序遍历的顺序。按照前序遍历的规则，首先访问根节点，然后递归访问左子树，再递归访问右子树。对于这棵树，遍历的顺序是：1 → 2 → 4 → 5 → 3 → 6 → 7。

• 中序遍历（In-order）：访问左子树，再访问根节点，最后访问右子树。 如图: 这是树的中序遍历示意图，红色数字表示中序遍历的顺序。按照中序遍历的规则，首先递归访问左子树，然后访问根节点，最后递归访问右子树。对于这棵树，遍历的顺序是：4 → 2 → 5 → 1 → 6 → 3 → 7。

• 后序遍历（Post-order）：访问左子树，再访问右子树，最后访问根节点。 如图:

• 层序遍历（Level-order）：从上到下、从左到右按层次遍历。

总结：

• 树是一种非线性的数据结构，每个节点可以有多个子节点。
• 二叉树是一种特定类型的树结构，每个节点最多有两个子节点。二叉树有许多变种，如二叉搜索树、平衡二叉树等，它们在算法和数据结构中起着至关重要的作用。

这些概念是理解更多高级数据结构和算法的基础，尤其在处理搜索、排序和动态规划等问题时，非常有用。

2.完全二叉树

完全二叉树是一种特殊的二叉树，它具有以下特点：

1. 每一层节点都要填满：除了最后一层外，完全二叉树的每一层都必须是满的，也就是说，除了最底层，其他层的节点数都达到最大值。

2. 最后一层的节点尽量靠左：最后一层的节点从左到右依次排列，不能有空缺。也就是说，最后一层的节点虽然可以不满，但必须尽量靠左对齐。

完全二叉树的一个重要特点是，它是非常紧凑的结构，不像普通二叉树那样可能会出现大量的空白位置。由于这一特性，完全二叉树通常用于堆数据结构（例如最大堆或最小堆）中，因为在这种树形结构下，插入和删除节点的操作效率较高。

举例说明

假设有7个节点，它们按顺序排列构建成完全二叉树，结果如下：

        1
      /   \
     2     3
    / \   / 
   4   5 6 

• 这棵树的第1层有1个节点，第2层有2个节点，第3层有3个节点。
• 最后一层的节点6和7是从左到右依次排列的，没有空缺。

总结来说，完全二叉树是一种节点密集且结构紧凑的树形结构，它满足每一层都完全填充，且最后一层节点尽可能集中在左边。

题解：求完全二叉树的最大路径和

题目描述

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

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

思路解析

本题的核心思想是使用递归遍历完全二叉树，每次从一个节点开始，递归地计算从该节点到叶子节点的最大路径和。以下是详细的思路解析及对应的代码。

1. 树的结构与索引关系：
   • 给定的数组是完全二叉树的层序遍历结果。
   • 根节点对应数组中的第一个元素。
   • 对于数组中第 ( i ) 个元素：
     • 左子节点的索引是 ( 2i + 1 )
     • 右子节点的索引是 ( 2i + 2 )
   • 叶子节点是没有子节点的节点。对于一个节点 ( i )，如果 ( 2i + 1 \geq n )，那么它就是叶子节点（即它的左子节点的索引已经超出了数组的范围）。这也是递归终止的条件。

对应代码：

left_index = 2 * index + 1
right_index = 2 * index + 2

通过这两个公式可以找到当前节点的左子节点和右子节点。

2. 递归算法：
   • 从根节点开始，递归地遍历每个节点，计算从当前节点到叶子节点的路径和。
   • 对每个节点，分别计算它的左子树和右子树的最大路径和。
   • 如果节点是叶子节点，直接返回它的值。
   • 返回当前节点的最大路径和时，选择左子树和右子树的较大路径和加上当前节点的值。

对应代码：

def maxPathSum(arr, index, n):
    # 计算当前节点的左子节点和右子节点的索引
    left_index = 2 * index + 1
    right_index = 2 * index + 2

    # 如果是叶子节点
    if left_index >= n and right_index >= n:
        return arr[index]

首先，计算当前节点的左右子节点索引，如果当前节点没有子节点，则它是叶子节点，直接返回当前节点的值。

3. 递归条件：计算左子树和右子树的路径和：
   • 如果左子树存在，递归计算左子树的最大路径和。
   • 如果右子树存在，递归计算右子树的最大路径和。

对应代码：

left_sum = 0
right_sum = 0

# 如果左子树存在，递归计算左子树的最大路径和
if left_index < n:
    left_sum = maxPathSum(arr, left_index, n)

# 如果右子树存在，递归计算右子树的最大路径和
if right_index < n:
    right_sum = maxPathSum(arr, right_index, n)

通过判断当前节点是否有左子节点和右子节点，分别递归计算左右子树的最大路径和。

4. 计算当前节点的最大路径和：
   • 返回当前节点的值加上左右子树的最大路径和。也就是从当前节点到任意叶子节点的路径和。

对应代码：

# 返回当前节点的值加上左右子树最大路径和
return arr[index] + max(left_sum, right_sum)

最终返回当前节点的路径和，选择左右子树中较大的路径和加上当前节点的值。

Python代码实现

def maxPathSum(arr, index, n):
    # 计算当前节点的左子节点和右子节点的索引
    left_index = 2 * index + 1
    right_index = 2 * index + 2

    # 如果是叶子节点，直接返回该节点的值
    if left_index >= n and right_index >= n:
        return arr[index]

    left_sum = 0
    right_sum = 0

    # 如果左子树存在，递归计算左子树的最大路径和
    if left_index < n:
        left_sum = maxPathSum(arr, left_index, n)

    # 如果右子树存在，递归计算右子树的最大路径和
    if right_index < n:
        right_sum = maxPathSum(arr, right_index, n)

    # 返回当前节点的值加上左右子树最大路径和
    return arr[index] + max(left_sum, right_sum)

# 主函数
if __name__ == "__main__":
    n = int(input())  # 输入节点数
    arr = list(map(int, input().split()))  # 输入完全二叉树的节点值
    
    # 从根节点开始计算最大路径和
    print(maxPathSum(arr, 0, n))

代码解释

1. 递归函数 maxPathSum：

   • 该函数用于计算从当前节点到叶子节点的最大路径和。
   • 基准条件：当节点是叶子节点时，直接返回该节点的值。
   • 递归计算：对于每个节点，递归计算其左右子树的最大路径和，最后返回当前节点的值加上左右子树的最大路径和。

2. 主函数：

   • 输入树的节点数量 ( n )，以及完全二叉树的节点值（用空格分隔）。
   • 调用 maxPathSum 函数从根节点开始计算最大路径和。

递归过程示例

假设输入为：

5
1 2 3 4 5

该数组表示一棵完全二叉树：

        1
       / \
      2   3
     / \
    4   5

递归过程如下：

1. 调用 maxPathSum(arr, 0, 5)，当前节点为 1，计算左子树和右子树的最大路径和。
2. 递归调用 maxPathSum(arr, 1, 5)，左子节点为 2，计算它的左子树和右子树路径和。
3. 递归调用 maxPathSum(arr, 3, 5)，当前节点为 4（叶子节点），返回 4。
4. 递归调用 maxPathSum(arr, 4, 5)，当前节点为 5（叶子节点），返回 5。
5. 计算左子树的最大路径和为 4，右子树的最大路径和为 5，因此返回 ( 2 + max(4, 5) = 7 )。
6. 递归调用 maxPathSum(arr, 2, 5)，右子节点为 3（叶子节点），返回 3。
7. 计算左子树的最大路径和为 7，右子树的最大路径和为 3，因此返回 ( 1 + max(7, 3) = 8 )。

最终返回结果为 8，表示从根节点到叶子节点的最大路径和为 8。

时间复杂度

• 每个节点最多被访问一次，因此时间复杂度为 O(n)，其中 ( n ) 是树中节点的数量。