1.简述:
二叉树里面的路径被定义为:从该树的任意节点出发,经过父=>子或者子=>父的连接,达到任意节点的序列。
注意:
1.同一个节点在一条二叉树路径里中最多出现一次
2.一条路径至少包含一个节点,且不一定经过根节点
给定一个二叉树,请你计算它的最大路径和
例如:
给出以下的二叉树,
最优路径是:2=>1=>3,或者3=>1=>2,最大路径和=2+1+3=6
数据范围:节点数满足 ,节点上的值满足
要求:空间复杂度 ,时间复杂度
第一行输入一个正整数 n 表示二叉树的节点数
第二行输入 n 个整数表示二叉树上第 i 个节点的值
第三行输入 n 个整数表示二叉树上第 i 个节点的父节点是第几个节点,(其中第一个节点是根节点,其父节点表示为第零个节点0)。
输出最大路径和
输入:
3
1 2 3
0 1 1
输出:
6
输入:
5
-20 8 20 15 6
0 1 1 3 3
输出:
41
说明:
其中一条最大路径为:15=>20=>6,路径和为15+20+6=41
输入:
2
-2 -3
0 1
输出:
-2
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);
}
}