1. 首页

LeetCode 125. 验证回文串

题目描述


给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: 输入:[1,2,3] 1 / \ 2 3 输出:6 示例 2: 输入:[-10,9,20,null,null,15,7]   -10    / \   9  20     /  \    15   7 输出:42

难度:Middle

前置知识

  • 递归

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这道题目的 path 让我误解了,然后浪费了很多时间来解这道题
我觉得 leetcode 给的 demo 太少了,不足以让我理解 path 的概念
因此我这里自己画了一个图,来补充一下,帮助大家理解 path 的概念,不要像我一样理解错啦。

首先是官网给的两个例子:

124.binary-tree-maximum-path-sum

接着是我自己画的一个例子:

124.binary-tree-maximum-path-sum

如图红色的部分是最大路径上的节点。大家可以结合上面的 demo 来继续理解一下 path, 除非你理解了 path,否则不要往下看。

树的题目,基本都是考察递归思想的。因此我们需要思考如何去定义我们的递归函数,在这里我定义了一个递归函数,它的功能是,返回以当前节点为根节点的MaxPath

但是有两个条件:

  1. 根节点必须选择
  2. 左右子树只能选择一个

为什么要有这两个条件?

我的想法是原问题可以转化为:以每一个节点为根节点,分别求出 MaxPath,最后计算最大值,因此第一个条件需要满足.

对于第二个条件,由于递归函数子节点的返回值会被父节点使用,因此我们如果两个孩子都选择了就不符合 MaxPath 的定义了。实际上这道题,当遍历到某一个节点的时候,我们需要子节点的信息,然后同时结合自身的 val 来决定要不要选取左右子树以及选取的话要选哪一个, 因此这个过程本质上就是后序遍历

基本算法就是不断调用递归函数,然后在调用过程中不断计算和更新 MaxPath,最后在主函数中将 MaxPath 返回即可。

关键点解析

  • 递归
  • 理解题目中的 path 定义

代码

代码支持:JavaScript,Java,Python

  • JavaScript
/*
 * @lc app=leetcode id=124 lang=javascript
 *
 * [124] Binary Tree Maximum Path Sum
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
function helper(node, payload) {
  if (node === null) return 0;

  const l = helper(node.left, payload);
  const r = helper(node.right, payload);

  payload.max = Math.max(
    node.val + Math.max(0, l) + Math.max(0, r),
    payload.max
  );

  return node.val + Math.max(l, r, 0);
}
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function (root) {
  if (root === null) return 0;
  const payload = {
    max: root.val,
  };
  helper(root, payload);
  return payload.max;
};
  • Java
/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  int ans;
  public int maxPathSum(TreeNode root) {
    ans = Integer.MIN_VALUE;
    helper(root);   // recursion
    return ans;
  }

  public int helper(TreeNode root) {
    if (root == null) return 0;
    int leftMax = Math.max(0, helper(root.left));     // find the max sub-path sum in left sub-tree
    int rightMax = Math.max(0, helper(root.right));   // find the max sub-path sum in right sub-tree
    ans = Math.max(ans, leftMax+rightMax+root.val);   // find the max path sum at current node
    return max(leftMax, rightMax) + root.val;         // according to the definition of path, the return value of current node can only be that the sum of current node value plus either left or right max path sum.
  }
}
  • Python

class Solution: ans = float('-inf') def maxPathSum(self, root: TreeNode) -> int: def helper(node): if not node: return 0 l = helper(node.left) r = helper(node.right) self.ans = max(self.ans, max(l,0) + max(r, 0) + node.val) return max(l, r, 0) + node.val helper(root) return self.ans

复杂度分析

  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$

相关题目

更多题解可以访问我的 JS中文网 – 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 125. 验证回文串

链接:https://www.javascriptc.com/4489.html

« LeetCode 126. 单词接龙 II
「 volute 」树莓派+带你使用Node.js打造一个有灵魂的语音助手»
Flutter 中文教程资源

相关推荐

QR code