`
blue2048
  • 浏览: 183620 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

[leetcode]Binary Tree Maximum Path Sum - java 后续遍历

阅读更多

这道题估计难在审题上,题目描述太简单了,导致提交各种情况没想到,整个代码比较简单,可以解释题目,采用递归后续遍历的方式,从叶子节点开始算起,每次计算产生两个值,一个是最大通路值(maxPathSum ),一个是子树能为父节点提供的最大单支值(findSingleBranchMaxPathSum递归返回的值)

 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private Integer maxPathSum = null;

    public int maxPathSum(TreeNode root){
        findSingleBranchMaxPathSum(root);
        return maxPathSum;
    }

    private int findSingleBranchMaxPathSum(TreeNode root) {
        int leftMaxPathSum=0;
        int rightMaxPathSum=0;
        if(root.left != null){
            leftMaxPathSum = findSingleBranchMaxPathSum(root.left);
        }
        if(root.right != null){
            rightMaxPathSum = findSingleBranchMaxPathSum(root.right);
        }
        int left = leftMaxPathSum<0?0:leftMaxPathSum;
        int right = rightMaxPathSum<0?0:rightMaxPathSum;
        if(maxPathSum == null){
            maxPathSum = root.val+left+right;
        }else if(root.val+left+right>maxPathSum){
            maxPathSum = root.val+left+right;
        }
        int single = left>right?left:right;
        return root.val+single;
    }
}

 

 

 

分享到:
评论

相关推荐

    Algorithm-LeetCode-Solution-From-GuaZiDou.zip

    再如,"Binary Tree Maximum Path Sum"问题,要求找到二叉树中从根节点到叶子节点的最大路径和。这个问题可以通过深度优先搜索或广度优先搜索结合动态规划来解决。 GuaZiDou的解决方案不仅包含了代码实现,通常还...

    四平方和定理leetcode-leetcode-practice:个人LeetCode练习代码

    104.maximum-depth-of-binary-tree (二叉树的最大深度) 105.construct-binary-tree-from-preorder-and-inorder-traversal (从前序与中序遍历序列构造二叉树) 106.construct-binary-tree-from-inorder-and-postorder-...

    Leetcode题目+解析+思路+答案.pdf

    - **Binary Tree Path**:找到二叉树中和为目标值的路径。 - **Sum Root to Leaf Numbers**:计算二叉树所有从根到叶子节点的路径之和。 4. **动态规划(Dynamic Programming)**: - **Best Time To Buy and ...

    leetcode-answer-and-analysis(part).zip_图形图像处理_Java_

    7. **Binary Tree Maximum Path Sum** (二叉树中的最大路径和): 这是一道深度优先搜索(DFS)问题,寻找从根节点到任意叶子节点的最大路径和。在Java中,可以递归地访问每个节点并更新最大路径。 8. **Insertion ...

    Leetcode book刷题必备

    31. Binary Tree Maximum Path Sum:二叉树中的最大路径和。 32. Binary Tree Upside Down:将一个二叉树进行翻转。 【位操作】 33. Single Number:找出数组中唯一不出现一次的数字。 34. Single Number II:找出...

    leetcode答案-leetcode-[removed]用javascript刷LeetCode

    例如,"Binary Tree Maximum Path Sum"(二叉树最大路径和)问题,我们可以使用DFS来计算每个节点到根节点的路径和,然后比较并返回最大值。 在"leetcode-javascript-master"这个压缩包中,很可能包含了作者使用...

    常见算法题答案及解析

    31. Binary Tree Maximum Path Sum:二叉树中的最大路径和。 32. Binary Tree Upside Down:将二叉树进行上下翻转。 五、位运算 33. Single Number:只出现一次的数字,要求不使用额外空间。 34. Single Number II...

    Leetcode

    还有一些更高级的问题,如 "Binary Tree Maximum Path Sum",它涉及到树的深度优先搜索(DFS)或广度优先搜索(BFS),以及动态规划的策略。这类问题需要理解如何构建和遍历二叉树,并计算路径的最大和。 LeetCode...

    leetcode

    3. "Binary Tree Maximum Path Sum"(二叉树最大路径和):这题需要用到深度优先搜索,同时结合动态规划的思想,寻找一条路径使得经过的所有节点的路径和最大。 五、LeetCode对Java开发者的意义 1. 提升技能:...

    LeetCode:用于测试来自https的问题

    "Binary Tree Maximum Path Sum"则可能涉及到深度优先搜索或广度优先搜索等树遍历策略。 此外,C#的特性如委托、事件、匿名函数、LINQ等也可能在LeetCode的C#解决方案中得到体现。例如,LINQ(Language Integrated ...

    LeetCode:解决LeetCode的问题

    对于更复杂的题目,如"Binary Tree Maximum Path Sum"(二叉树的最大路径和),我们需要掌握深度优先搜索(DFS)或广度优先搜索(BFS)策略,同时理解和运用树的性质。在这个问题中,我们需要沿着一条路径递归地访问...

    LeetcodeSolutions:我收集的评论很好的leetcode问题解决方案

    而"Binary Tree Maximum Path Sum"(二叉树最大路径和)这类问题则需要结合深度优先搜索来找到最大路径。 在"Merge Intervals"(合并区间)问题中,我们需要对区间进行排序,然后利用双指针技术合并重叠部分,这...

    LeetCode:收集LeetCode问题以使编码面试更加出色!

    另一个例子是“Binary Tree Maximum Path Sum”,需要你找到二叉树中具有最大路径和的路径,这涉及到递归和树的遍历。 解决LeetCode问题的过程中,你还可以学习如何编写清晰、简洁且易于理解的代码,这是面试官非常...

    leetcode-practice:解决问题的实践; 数据结构和算法审查

    又如,"Binary Tree Maximum Path Sum"需要找出二叉树中的最大路径和,这就需要用到深度优先搜索和递归。 此外,LeetCode还涵盖了字符串处理、位操作、数学逻辑等多方面的知识。通过不断地练习和挑战,我们可以深入...

    leetCode:Leetcode解决方案

    例如,Binary Tree Preorder Traversal(二叉树前序遍历)和Shortest Path in Binary Matrix(二进制矩阵中最短路径)等。 二、算法策略 1. 搜索:深度优先搜索(DFS)和广度优先搜索(BFS)是解决许多问题的有效...

    LeetCode:LeetCode上一些算法的解答

    5. **二叉树**:二叉树问题包括遍历、查找、平衡调整等,如"二叉树的最大路径和"(Maximum Path Sum)、"验证二叉搜索树"(Validate Binary Search Tree)。 6. **回溯**:回溯是一种尝试所有可能解的算法策略,...

    leetcode:我的leetcode培训。 实践使完美!

    "二叉树的最大路径和"(Maximum Depth of Binary Tree)是其中的一例。 5. **堆栈和队列**:如实现栈或队列的功能,或者使用它们解决实际问题。"有效括号"(Valid Parentheses)要求使用栈来检查括号匹配性。 6. *...

    LeetCode

    例如,“二叉树的最大路径和”(Maximum Depth of Binary Tree)计算二叉树的最大深度。 6. **图(Graphs)**:遍历、最短路径、拓扑排序等问题。如“最短路径问题”(Shortest Path in a Grid with Obstacles ...

Global site tag (gtag.js) - Google Analytics