1.简述：

描述
二叉树里面的路径被定义为:从该树的任意节点出发，经过父=>子或者子=>父的连接，达到任意节点的序列。

注意:

1.同一个节点在一条二叉树路径里中最多出现一次

2.一条路径至少包含一个节点，且不一定经过根节点

给定一个二叉树，请你计算它的最大路径和

例如：

给出以下的二叉树，

最优路径是:2=>1=>3，或者3=>1=>2，最大路径和=2+1+3=6

数据范围：节点数满足  ，节点上的值满足

要求：空间复杂度 ，时间复杂度

输入描述：
第一行输入一个正整数 n 表示二叉树的节点数

第二行输入 n 个整数表示二叉树上第 i 个节点的值

第三行输入 n 个整数表示二叉树上第 i 个节点的父节点是第几个节点，（其中第一个节点是根节点，其父节点表示为第零个节点0）。

输出描述：
输出最大路径和

示例1
输入：

3
1 2 3
0 1 1
1.
2.
3.
输出：

6
1.
示例2
输入：

5
-20 8 20 15 6
0 1 1 3 3
1.
2.
3.
输出：

41
1.
说明：

其中一条最大路径为:15=>20=>6，路径和为15+20+6=41
1.
示例3
输入：

2
-2 -3
0 1
1.
2.
3.
输出：

-2
1.
2.代码实现：

登录后复制
import java.util.Scanner;

public class Main{

public static void main(String[] args){
int n;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
int[] node = new int[n];
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
node[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
parent[i] = sc.nextInt();
}

// 记录子节点
int[][] child = new int[n][2];

for (int i = 0; i < n; i++) {
child[i][0] = child[i][1] = -1;

if (parent[i] > 0) {
int[] childNode = child[parent[i] – 1];
if (childNode[0] == -1) {
childNode[0] = i;
} else {
childNode[1] = i;
}
}
}

int max = node[0];
int[] dp = new int[n];
// 从子节点往父节点记录dp
for (int i = n – 1; i >= 0; i–) {
int left = 0, right = 0;
if (child[i][0] != -1)
left = dp[child[i][0]];
if (child[i][1] != -1)
right = dp[child[i][1]];
dp[i] = Math.max(Math.max(left, right), 0) + node[i];
max = max(max, node[i], node[i] + left, node[i] + right, node[i] + left + right);
}
System.out.println(max);

}

public static int max(int a, int b, int c, int d, int e) {
return Math.max(Math.max(Math.max(Math.max(a, b), c), d), e);
}
}