首页 > 其他分享 >Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

时间:2024-03-09 15:35:24浏览次数:34  
标签:Binary right TreeNode int max Sum 路径 Tree root

Source

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,

       1
      / \
     2   3
Return 6.

题解1 - 递归中仅返回子树路径长度

题目很短,要求返回最大路径和。咋看一下感觉使用递归应该很快就能搞定,实则不然,因为从题目来看路径和中不一定包含根节点!也就是说可以起止于树中任一连通节点。

弄懂题意后我们就来剖析剖析,本着由简入难的原则,我们先来分析若路径和包含根节点,如何才能使其路径和达到最大呢?选定根节点后,路径和中必然包含有根节点的值,剩下的部分则为左子树和右子树,要使路径和最大,则必然要使左子树和右子树中的路径长度都取最大。

!注意区分包含根节点的路径和(题目要的答案)和左子树/右子树部分的路径长度(答案的一个组成部分)。路径和=根节点+左子树路径长度+右子树路径长度

       -10
       /  \
      2    -3
     / \   / \
    3   4 5   7

如上所示,包含根节点-10的路径和组成的节点应为4 -> 2 -> -10 <- -3 <- 7, 对于左子树而言,其可能的路径组成节点为3 -> 2或4 -> 2, 而不是像根节点的路径和那样为3 -> 2 <- 4. 这种差异也就造成了我们不能很愉快地使用递归来求得最大路径和。

我们使用分治的思想来分析路径和/左子树/右子树,设 f(root) 为 root 的子树到 root 节点(含)路径长度的最大值,那么我们有 f(root)=root−>val+max(f(root−>left), f(root−>right))

递归模型已初步建立起来,接下来就是分析如何将左右子树的路径长度和最终题目要求的「路径和」挂钩。设 g(root) 为当「路径和」中根节点为 root 时的值,那么我们有g(root)=root−>val+f(root−>left)+f(root−>right)

顺着这个思路,我们可以遍历树中的每一个节点求得 g(node) 的值,输出最大值即可。如果不采取任何记忆化存储的措施,其时间复杂度必然是指数级别的。嗯,先来看看这个思路的具体实现,后续再对其进行优化。遍历节点我们使用递归版的前序遍历,求单边路径长度采用递归。

Time Limit Exceeded

/**
 * 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) {
        if (NULL == root) {
            return 0;
        }

        int result = INT_MIN;
        stack<TreeNode *> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode *node = s.top();
            s.pop();

            int temp_path_sum = node->val + singlePathSum(node->left) \
                                          + singlePathSum(node->right);

            if (temp_path_sum > result) {
                result = temp_path_sum;
            }

            if (NULL != node->right) s.push(node->right);
            if (NULL != node->left) s.push(node->left);
        }

        return result;
    }

private:
    int singlePathSum(TreeNode *root) {
        if (NULL == root) {
            return 0;
        }

        int path_sum = max(singlePathSum(root->left), singlePathSum(root->right));
        return max(0, (root->val + path_sum));
    }
};

源码分析

注意singlePathSum中最后的返回值,如果其路径长度path_sum比0还小,那么取这一段路径反而会减少最终的路径和,故不应取这一段,我们使用0表示这一隐含意义。

题解2 - 递归中同时返回子树路径长度和路径和

C++ using std::pair

上题求路径和和左右子树路径长度是分开求得的,因此导致了时间复杂度剧增的恶劣情况,从题解的递推关系我们可以看出其实是可以在一次递归调用过程中同时求得路径和和左右子树的路径长度的,只不过此时递归程序需要返回的不再是一个值,而是路径长度和路径和这一组值!C++中我们可以使用 pair 或者自定义新的数据类型来相对优雅的解决。

 

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
private:
    pair<int, int> helper(TreeNode *root) {
        if (NULL == root) {
            return make_pair(0, INT_MIN);
        }

        pair<int, int> leftTree = helper(root->left);
        pair<int, int> rightTree = helper(root->right);

        int single_path_sum = max(leftTree.first, rightTree.first) + root->val;
        single_path_sum = max(0, single_path_sum);

        int max_sub_sum = max(leftTree.second, rightTree.second);
        int max_path_sum = root->val + leftTree.first + rightTree.first;
        max_path_sum = max(max_sub_sum, max_path_sum);

        return make_pair(single_path_sum, max_path_sum);
    }

public:
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    int maxPathSum(TreeNode *root) {
        if (NULL == root) {
            return 0;
        }

        return helper(root).second;
    }
};

源码分析

除了使用pair对其进行封装,也可使用嵌套类新建一包含单路径长度和全局路径和两个变量的类,不过我用 C++写的没编译过... 老是提示...private,遂用pair改写之。建议使用class而不是pair封装single_path_sum和max_path_sumpair_is_harmful.

这种方法难以理解的地方在于这种实现方式的正确性,较为关键的语句为max_path_sum = max(max_sub_sum, max_path_sum), 这行代码是如何体现题目中以下的这句话的呢?

The path may start and end at any node in the tree.

简单来讲,题解2从两个方面予以保证:

采用「冒泡」法返回不经过根节点的路径和的较大值。
递推子树路径长度(不变值)而不是到该节点的路径和(有可能变化),从而保证了这种解法的正确性。
如果还不理解的建议就以上面那个根节点为-10的例子画一画。

C++

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
    class ResultType {
    public:
        int singlePath, maxPath;
        ResultType(int s, int m):singlePath(s), maxPath(m) {}
    };

private:
    ResultType helper(TreeNode *root) {
        if (root == NULL) {
            ResultType *nullResult = new ResultType(0, INT_MIN);
            return *nullResult;
        }
        // Divide
        ResultType left = helper(root->left);
        ResultType right = helper(root->right);

        // Conquer
        int singlePath = max(left.singlePath, right.singlePath) + root->val;
        singlePath = max(singlePath, 0);

        int maxPath = max(left.maxPath, right.maxPath);
        maxPath = max(maxPath, left.singlePath + right.singlePath + root->val);

        ResultType *result = new ResultType(singlePath, maxPath);
        return *result;
    }

public:
    int maxPathSum(TreeNode *root) {
        ResultType result = helper(root);
        return result.maxPath;
    }
};

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Result {
    int singlePath, maxPath;
    Result(int singlePath, int maxPath) {
        this.singlePath = singlePath;
        this.maxPath = maxPath;
    }
}

public class Solution {
    public int maxPathSum(TreeNode root) {
        return helper(root).maxPath;
    }

    private Result helper(TreeNode root) {
        if (root == null) {
            // maxPath should be MIN_VALUE to avoid negtive
            return new Result(0, Integer.MIN_VALUE);
        }

        Result left = helper(root.left);
        Result right = helper(root.right);

        int singlePath = Math.max(left.singlePath, right.singlePath) + root.val;
        singlePath = Math.max(0, singlePath); // drop negtive

        int maxPath = Math.max(left.maxPath, right.maxPath);
        maxPath = Math.max(maxPath, root.val + left.singlePath + right.singlePath);

        return new Result(singlePath, maxPath);
    }
}

源码分析

1、如果不用 ResultType *XXX = new ResultType ... 再 return *XXX 的方式,则需要在自定义 class 中重载 new operator。
2、如果遇到 ...private 的编译错误,则是因为自定义 class 中需要把成员声明为 public,否则需要把访问这个成员的函数也做 class 内部处理。

 

 

 

标签:Binary,right,TreeNode,int,max,Sum,路径,Tree,root
From: https://www.cnblogs.com/lyc94620/p/18062757

相关文章

  • CF1846D Rudolph and Christmas Tree 题解
    因为\(n\)个三角形有重叠部分,所以我们可以倒序处理每个三角形,并对其进行分类讨论:若当前三角形编号为\(n\),则直接将总面积加上\(\dfrac{d\timesh}{2}\)。否则,再次分出两种情况:若当前三角形的\(y_i+h>y_{i+1}\)(即编号为\(i,i+1\)的三角形有重叠),则如下图所示:......
  • TreeMap练习
    TreeMap练习1."aababcabcdabcde",获取字符串中每一个字母出现的次数要求结果:a(5)b(4)c(3)d(2)e(1)packagecom.shujia.day14;importjava.util.Map;importjava.util.Set;importjava.util.TreeMap;publicclassTreeMapTest1{publicstaticvoidmain(String[]arg......
  • Compressed Tree
    首先官方题解写的挺好的,可以看为什么需要在DP状态中定义\(i\)及其父亲的这条边也在呢?你可以试试不定义,那么你会发现是推不走的,因为比如我们现在正在推\(i\),那么他的一个儿子\(u\)的DP值都知道了,但是由于有了\((u,i)\)这一条边,我们就把\(u\)的度数改变了,这个时候\(u\)的DP值就不在......
  • [HDU6647] Bracket Sequences on Tree 题解
    [HDU6647]BracketSequencesonTree题解一道纯靠自己推出来的换根\(dp+\)树哈希,写篇题解庆祝一下~~题意:给定一棵无根树,你可以任意选择根节点和遍历顺序,每次遍历时进入一个节点就标记一个(,离开一个节点就标记一个),问所有存在的括号序列有多少种,对998244353取模。先考虑根固......
  • 「AGC005B」 Minimum Sum
    题意给定一个整数序列\(a\),求\(\sum\limits^{N}_{l=1}\sum\limits^{N}_{r=l}\min(a_l,a_{l+1},\cdots,a_{r})\)(注意\(r\)的初始值是\(l\))。分析当我们模拟样例时,可以发现,每一个数都只会在一个区间内最小,而最小值不断更新成更小的,所以可以用单调栈求解出\(a_i\)对应......
  • 【学习笔记】 - 基础数据结构 :Link-Cut Tree(进阶篇)
    前言LCT没题写可以去写树剖和一些线段树合并的题练手LCT的概念原本的树剖是对树进行剖分,剖分为重边和轻边LCT则是对于树分为虚边和实边,特殊的,LCT可以没有虚边(例:银河英雄传说v2)单独被包含在一个实链里的点称作孤立点在树剖中,我们使用线段树/树状数组来维护重链在Link-Cut......
  • 说说Vue 3.0中Treeshaking特性?举例说明一下?
    这里给大家分享我在网上总结出来的一些知识,希望对大家有所帮助 一、是什么Treeshaking 是一种通过清除多余代码方式来优化项目打包体积的技术,专业术语叫 Deadcodeelimination简单来讲,就是在保持代码运行结果不变的前提下,去除无用的代码如果把代码打包比作制作蛋糕,传统......
  • 向TreeView添加自定义信息
    可在Windows窗体TreeView控件中创建派生节点,或在ListView控件中创建派生项。通过派生可添加任何所需字段,以及添加处理这些字段的自定义方法和构造函数。此功能的用途之一是将Customer对象附加到每个树节点或列表项。虽然此处的示例是关于TreeView控件的,但该方法同样......
  • CF1066E Binary Numbers AND Sum 题解
    分析因为\(a\)是一直没有改变的,移动的只有\(b\),所以从\(a\)的每一位的贡献入手。对于\(a\)中的从低到高第\(i\)位,其对应的十进制值是\(a_{n-i+1}\times2^{i-1}\)。注意到\(b\)是每次右移一位的,所以在\(b\)中能与\(a_{n-i+1}\)匹配的都是在下标区间\([1,m-i+1]......
  • el-tree数据量过大导致页面卡顿
    问题:el-tree等树形结构,当数据量非常大,渲染会很慢解决方案:懒加载方法:设置lazy属性为true,当点击父级节点时,再通过load方法加载子列表。优点:使用简单。缺点:不能做回显,无法展开全部节点。虚拟列表方法:使用插件或者自己实现一个虚拟列表(推荐:https://sangtian152.github.io/v......