二叉树最大路径和问题

二叉树,最大,路径,问题 · 浏览次数 : 48

小编点评

**二叉树最大路径和** **题目描述** 给定一个二叉树的根节点 `root` ，请返回其最大路径和。 **主要思路** 通过递归地访问树中的子节点，我们可以求得树的最大路径和。在每次递归过程中，我们记录当前路径和的最大路径和。当我们访问子节点时，如果其子树的路径和大于当前路径和，则更新当前路径和。最后，我们返回树的路径和最大路径和。 **代码** ```python class Info: def __init__(self, path, head): self.maxPathSum = path self.maxPathSumFromHead = head def maxPathSum(root: TreeNode) -> int: if root is None: return 0 # 递归处理左右子树 left_info = maxPathSum(root.left) right_info = maxPathSum(root.right) # 更新当前路径和最大路径和 maxPathSum = max(left_info.maxPathSum, right_info.maxPathSum) maxPathSum = max(maxPathSum, root.val + max(left_info.maxPathSum, right_info.maxPathSum)) return maxPathSum ``` **复杂度** 时间复杂度为 O(n)，其中 n 是树的节点数。这是因为我们在每个节点上递归执行一次，并记录路径和的最大路径和。 **空间复杂度** 空间复杂度为 O(h)，其中 h 是树的高度。这是因为我们在每个节点上递归执行一次，并记录路径和的最大路径和。

正文

二叉树最大路径和问题

作者：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变量有如下几种情况

只包含 head.val,这种情况暗示左右子树汇报的maxPathSumFromHead均为负数；
包含head.val和左子树的maxPathSumFromHead，这种情况暗示右子树的maxPathSumFromHead小于0，且左子树的maxPathSumFromHead大于0。

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

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

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

只包含leftInfo.maxPathSum;
只包含rightInfo.maxPathSum;
只包含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);
  }
}

算法和数据结构笔记