lintcode94. 二叉树中的最大路径和

小咪咪 2023-07-04 11:15 5阅读 0赞

给出一棵二叉树，寻找一条路径使其路径和最大，路径可以在任一节点中开始和结束（路径和为两个节点之间所在路径上的节点权值之和）

样例
    样例 1:
    	输入:  给定一棵树（只有一个节点）:
    	2
    	输出：2
    	
    样例 2:
    	输入:  给定一棵树：
    
          1
         / \
        2   3
    		
    	输出: 6

/**
     * Definition of TreeNode:
     * class TreeNode {
     * public:
     *     int val;
     *     TreeNode *left, *right;
     *     TreeNode(int val) {
     *         this->val = val;
     *         this->left = this->right = NULL;
     *     }
     * }
     */
    
    class Solution {
        
    public:
        /**
         * @param root: The root of binary tree.
         * @return: An integer
         */
        int maxPathSum(TreeNode * root) {
        
            // write your code here
            int max=INT_MIN;
            recursion(root,max);
            return max;
        }
        int recursion(TreeNode*root,int &maxs)
        {
        
            if(root==NULL) return 0;
            int left=recursion(root->left,maxs);
            int right=recursion(root->right,maxs);
            maxs=max(maxs,max(0,left)+max(0,right)+root->val);
            return max(left,right)+root->val;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，5人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_二叉树_困难_124. 二叉树中的最大路径和

目录 1.题目 2.思路 3.代码实现（Java） 1.题目路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一

港控/mmm°/ 2023年10月06日 22:43/ 0 赞/ 21 阅读

相关 lintcode94. 二叉树中的最大路径和

给出一棵二叉树，寻找一条路径使其路径和最大，路径可以在任一节点中开始和结束（路径和为两个节点之间所在路径上的节点权值之和）样例样例 1: 输入:

小咪咪/ 2023年07月04日 11:15/ 0 赞/ 6 阅读

相关 124二叉树中的最大路径和

一、前言标签：树\_最大路径。问题来源LeetCode 124 难度：困难。问题链接：[https://leetcode-cn.com/problems/bin

末蓝、/ 2023年03月01日 12:27/ 0 赞/ 141 阅读

相关二叉树中的最大路径和

二叉树中的最大路径和 -------------------- 路径和：二叉树的任意两节点经过中间若干节点（当然也可能中间没有节点，另外单个节点也可看作路径，这里理解

本是古典何须时尚/ 2023年02月20日 02:53/ 0 赞/ 99 阅读

相关二叉树之求二叉树中最大路径和

LeetCode中一道求二叉树中最大路径和的题目，一起来复习下二叉树的遍历。以如图所示二叉树为例 ![在这里插入图片描述][2020060215091962.bmp]

朱雀/ 2023年02月14日 10:41/ 0 赞/ 150 阅读

相关二叉树中的最大路径和

一、前言里面来源LeetCode 124，难度：困难问题链接：[https://leetcode-cn.com/problems/binary-tree-maxim

缺乏、安全感/ 2023年02月10日 03:55/ 0 赞/ 12 阅读

相关 124. 二叉树中的最大路径和

题目： [124. 二叉树中的最大路径和][124.] [\[编程题\]二叉树的最大路径和][Link 1] ![在这里插入图片描述][watermark_typ

淩亂°似流年/ 2022年12月11日 12:26/ 0 赞/ 177 阅读

相关二叉树中的最大路径和

二叉树中的最大路径和 1、参考资料 https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

亦凉/ 2022年12月03日 11:25/ 0 赞/ 181 阅读

相关二叉树最大路径和

给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。 public

待我称王封你为后i/ 2022年10月27日 00:29/ 0 赞/ 196 阅读

相关 124. 二叉树中的最大路径和

> 路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

墨蓝/ 2022年10月10日 04:44/ 0 赞/ 176 阅读