【递归3】完全二叉树的最大路径和
前言
1.树以及二叉树的概念:
在算法和数据结构中,树和二叉树是非常重要的概念,下面我会简单介绍一下它们的基本概念。
题目描述:
给定一个数组表示一颗完全二叉树的节点值,其中数组下标 i 对应的节点值为 arr[i],左子节点的下标为 2i+1,右子节点的下标为 2i+2。你需要求出所有从根节点到叶子节点路径的最大路径和。
路径的定义是从根节点到任意叶子节点的路径,每个节点的值加上当前节点的值。
请你实现一个递归算法来计算所有路径中的最大路径和。
输入
- 输入的第一行是一个整数 n (1≤n≤105),表示数组 arr 的长度。
- 第二行是 n 个整数 arr0,arr1,...,arrn−1 (1≤arr[i]≤105),表示完全二叉树的节点值。
输出
样例
输入
5
1 2 3 4 5
输出
8
说明
1
/ \
2 3
/ \
4 5
- 所有路径如下:
- 从根节点到叶子节点的路径和分别是:
- 路径 1→2→4,和为 1+2+4=7
- 路径 1→2→5,和为 1+2+5=8
- 路径 1→3,和为 1+3=4
- 所有路径中的最大路径和是 8。