Binary Tree Maximum Path Sum

1，題目要求

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

在這里插入圖片描述
給定非空二叉樹，找到最大路徑總和。

對于此問題，路徑定義為沿著父子連接從樹中的某個起始節點到任何節點的任何節點序列。該路徑必須至少包含一個節點，并且不需要通過根節點。

2，題目思路

對于這道題，求一條樹中的路徑使得加和最大。

一顆樹的路徑，從一個開始節點出發，向上走0步或者k步，到達某一個根節點，然后再向下走0步或者k步。一旦它往下走，就不會再上升。因此，每條路徑都有一個最高節點，其也是這條路徑上其他所有節點的最低公共祖先。

在對這個問題的解決上，利用遞歸是比較方便的策略。
在遞歸的過程中，對于某一個節點，我們會遞歸地計算它的左子樹和右子樹的最大的路徑之和，然后判斷當前節點作為根節點時，路徑的值是否是當前所遍歷到的所有節點的最大值。
之后，我們返回這個節點作為上升或下降路徑的節點的值即可。

3，代碼實現

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

static const auto s = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int res = INT_MIN;
        maxPathHelper(root, res);
        return res;
        
    }
private:
    int maxPathHelper(TreeNode* node, int &res){
        if(node == nullptr)
            return 0;
        int left = max(0, maxPathHelper(node->left, res));
        int right= max(0, maxPathHelper(node->right,res));
        
        res = max(res, left + right + node->val);
        return max(left, right) + node->val;
    }
};

本文鏈接：https://blog.csdn.net/lym940928/article/details/90292903

智能推薦

lintcode94- Binary Tree Maximum Path Sum- medium

Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree. Example Given the below binary tree: return 6. 總結：二叉樹里起始點和終結點都任意的題目，其實可以考慮成接龍題。其實對于某個節點單...

【重點】LeetCode 124. Binary Tree Maximum Path Sum

LeetCode 124. Binary Tree Maximum Path Sum 參考鏈接：http://zxi.mytechroad.com/blog/tree/leetcode-124-binary-tree-maximum-path-sum/ Solution1： Time complexity O(n)O(n) Space complexity O(h)O(h) 代碼如下：花花醬講的...

Leetcode 124. Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connection...

LeetCode: 124. Binary Tree Maximum Path Sum

LeetCode: 124. Binary Tree Maximum Path Sum 題目描述 Given a binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the...

LeetCode 124. Binary Tree Maximum Path Sum

題目思路遞歸遍歷，找到左子樹和右子樹最大的路徑，返回加上當前節點的最大路徑即可。代碼...