LintCode 二叉树中的最大路径和题目分析代码

题目

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

样例 给出一棵二叉树:

Paste_Image.png

返回 6

分析

这道题关于二叉树的最大路径问题,显然需要用递归解决。 由于这道题中所求路径是可以通过根节点的,从任意节点开始和结束的最大路径和。 显然,通过根节点的最大路径=根节点的值,左子树的最大路径+右子树的最大路径 所以我们可以递归求解左右子树的最大路径,最后把他们加到一起就是整个树的最大路径。

代码

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
     

public int maxPathSum(TreeNode root) {
        if(root == null)
            return 0;
        ArrayList<Integer> res = new ArrayList<>();
        res.add(Integer.MIN_VALUE);
        helper(root, res);
        return res.get(0);
    }
    
    private int helper(TreeNode root, ArrayList<Integer> res) {
        if(root == null)
            return 0;
        int left = helper(root.left,res);
        int right = helper(root.right,res);
        
        int cur = root.val + (left>0?left:0) + (right>0?right:0);
        
        if(cur>res.get(0))
            res.set(0, cur);
        
        return root.val + Math.max(left, Math.max(right, 0));
    }
    
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏美团技术团队

红黑树深入剖析及Java实现

红黑树是平衡二叉查找树的一种。为了深入理解红黑树,我们需要从二叉查找树开始讲起。 BST 二叉查找树(Binary Search Tree,简称BST)是一棵二...

32930
来自专栏数据处理

236. Lowest Common Ancestor of a Binary Tree

23840
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之重建二叉树(九度OJ1385)

题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7...

22550
来自专栏数据处理

236. Lowest Common Ancestor of a Binary Tree

17650
来自专栏书山有路勤为径

二叉树-最近的公共祖先

已知二叉树,求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u,满足在树上最低(离根最 远),且v,w两个节点都是u的子孙。...

14620
来自专栏Java 源码分析

二叉树

1.二叉树的性质 1.具有 n 个节点的二叉树第 n 层最多2的 n-1 次方个节点 2.具有 n 个节点的二叉树最多有 2 的 n 次方减 1 个节点 3.度...

28040
来自专栏数据结构与算法

Day2平衡树笔记

线段树不支持的操作:删除,插入 ---- 常见的平衡树 treap 慢||好写 sbt(大小平衡的树) 非常快 比较好写 ||功能不全 rbt 红黑树 特...

32660
来自专栏灯塔大数据

每周学点大数据 | No.25二叉搜索树回顾(二)

No.25期 二叉搜索树回顾(二) Mr. 王:既然提到了有序的状态,那么我们就来谈谈有根树的遍历问题。 小可:我知道,遍历就是访问一个数据集合中的所...

35560
来自专栏开发 & 算法杂谈

PAT Advanced 1043

A Binary Search Tree (BST) is recursively defined as a binary tree which has th...

9230
来自专栏swag code

Calendar类-set()方法的延时操作

set(f,value)方法将日历字段f更改为value,此外还设置了一个内部成员变量,

7820

扫码关注云+社区

领取腾讯云代金券