二叉树最大路径和问题

作者：Grey

原文地址：

博客园：二叉树最大路径和问题

CSDN：二叉树最大路径和问题

题目描述

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

题目链接见: LeetCode 124. Binary Tree Maximum Path Sum

主要思路

本题使用二叉树递归套路方法，相关技巧见使用二叉树的递归套路来解决的问题

定义如下数据结构

  public static class Info {// 最大路径和public int maxPathSum;// 头结点一直往一侧扎，能扎到的最大值是多少public int maxPathSumFromHead;public Info(int path, int head) {maxPathSum = path;maxPathSumFromHead = head;}}

接下来定义递归函数

Info process(TreeNode head)

递归含义表示：head 为头的二叉树，得到的 Info 信息是什么。

主函数只需要调用

  public static int maxPathSum(TreeNode root) {if (root == null) {return 0;}return process(root).maxPathSum;}

即为要求的结果。

接下来就是process方法的实现，有如下几种情况

base case ，如果head == null，直接返回new Info(Integer.MIN_VALUE,Integer.MIN_VALUE)，不赘述。

接下来找左右子树的信息

    Info leftInfo = process(head.left);Info rightInfo = process(head.right);

整合成以 head 为头的树的信息，

其中以 head 为头的树的maxPathSumFromHead变量有如下几种情况

1. 只包含 head.val,这种情况暗示左右子树汇报的maxPathSumFromHead均为负数；

2. 包含head.val和左子树的maxPathSumFromHead，这种情况暗示右子树的maxPathSumFromHead小于0，且左子树的maxPathSumFromHead大于0。

以上两种情况都可以归结为

int maxPathSumFromHead =head.val + Math.max(Math.max(leftInfo.maxPathSumFromHead, rightInfo.maxPathSumFromHead), 0);

以 head 为头的树的maxPathSum包含如下几种情况

1. 只包含leftInfo.maxPathSum;

2. 只包含rightInfo.maxPathSum;

3. 只包含head.val + Math.max(0, leftInfo.maxPathSumFromHead) + Math.max(0, rightInfo.maxPathSumFromHead))

上述三种情况可以统一写成

int maxPathSum =Math.max(Math.max(leftInfo.maxPathSum, rightInfo.maxPathSum),head.val+ Math.max(0, leftInfo.maxPathSumFromHead)+ Math.max(0, rightInfo.maxPathSumFromHead));

完整代码见

class Solution {public static int maxPathSum(TreeNode root) {if (root == null) {return 0;}return process(root).maxPathSum;}// 任何一棵树，必须汇报上来的信息public static class Info {public int maxPathSum;public int maxPathSumFromHead;public Info(int path, int head) {maxPathSum = path;maxPathSumFromHead = head;}}public static Info process(TreeNode head) {if (null == head) {return new Info(Integer.MIN_VALUE, Integer.MIN_VALUE);}Info leftInfo = process(head.left);Info rightInfo = process(head.right);int maxPathSumFromHead =head.val + Math.max(Math.max(leftInfo.maxPathSumFromHead, rightInfo.maxPathSumFromHead), 0);int maxPathSum =Math.max(Math.max(leftInfo.maxPathSum, rightInfo.maxPathSum),head.val+ Math.max(0, leftInfo.maxPathSumFromHead)+ Math.max(0, rightInfo.maxPathSumFromHead));return new Info(maxPathSum, maxPathSumFromHead);}
}

更多

算法和数据结构笔记