二叉树最大路径和问题

二叉树最大路径和问题

作者：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);
  }
}

更多#

算法和数据结构笔记