【数据结构和算法】递归解决

二叉树的最大路径和

http://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a

这道题要求的最大路径和如果是从根节点开始到叶子节点就好办了,我们可以通过递归的方式,从下往上,舍去比较小的路径节点,保留比较大的节点。

但这道题要求的最大路径和并不一定经过根节点,如果再使用上面的方式就行不通了,对于这道题我们可以分为4种情况来讨论

1,只要当前节点,舍弃子节点。比如下面结点2的左右子节点都是负数,如果是负数我们还不如不要,所以直接舍弃子节点。

图片说明

2,保留当前节点和左子节点。比如下面结点2的右子节点是负数,我们直接舍弃右子节点,但左子节点不是负数,我们可以保留左子节点。

图片说明

3,保留当前节点和右子节点。比如下面结点2的左子节点是负数,我们直接舍弃左子节点,但右子节点不是负数,我们可以保留右子节点。
图片说明

4,保留当前节点和两个子节点。比如下面结点2的左右子节点都不是负数,我们都可以留下。
图片说明

上面的1,2,3都可以作为子树的一部分再继续计算,我们可以使用同一个公式,取左右子节点最大的那个即可,如果都小于0我们不要了,下面公式中left是左子树的值,right是右子树的值
图片说明

而4是不能在作为子树的一部分参与计算的,因为已经分叉了,比如下面的3→2→4是不能再和结点1进行组合的。第4种情况如果左右子树有一个是小于0的我们还不如不选,如果都大于0我们都要选的。

图片

图片说明

搞懂了上面的分析过程,代码就很容易写出来了,我们最后来看下代码

private int maxValue = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    maxPathSumHelper(root);
    return maxValue;
}

public int maxPathSumHelper(TreeNode root) {
    if (root == null)
        return 0;
    //左子节点的值
    int left = maxPathSumHelper(root.left);
    //右子节点的值
    int right = maxPathSumHelper(root.right);
    //第4种情况
    int cur = root.val + Math.max(0, left) + Math.max(0, right);
    //第1,2,3三种情况,返回当前值加上左右子节点的最大值即可,如果左右子节点都
    //小于0,还不如不选
    int res = root.val + Math.max(0, Math.max(left, right));
    //记录最大value值
    maxValue = Math.max(maxValue, Math.max(cur, res));
    //第1,2,3种情况还可以再计算,所以返回的是res
    return res;
}

时间复杂度:O(N),每个节点要有访问一遍。

空间复杂度:O(H),H是二叉树的最大高度,也是栈调用的深度,最差情况下二叉树倾斜成一个链表。


截止到目前我在公众号“数据结构和算法”中已经写了500多道算法题,其中部分已经整理成了pdf文档,目前总共有1000多页(并且还会不断的增加),大家可以免费下载
下载链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的《牛客博客》查看更多的详细题解

数据结构和算法 文章被收录于专栏

专注于算法题的讲解,包含常见数据结构,排序,查找,动态规划,回溯算法,贪心算法,双指针,BFS和DFS等等

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
2022-12-31 21:37
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
6 1 评论
分享

全站热榜

正在热议