#yyds干货盘点# 动态规划专题：二叉树中的最大路径和

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

输出：

6

示例2

输入：

5
-20 8 20 15 6
0 1 1 3 3

输出：

41

说明：

其中一条最大路径为:15=>20=>6，路径和为15+20+6=41

示例3

输入：

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);
    }
}