当前位置:   article > 正文

leetcode题库124-- 二叉树中的最大路径和_如果要将二叉树{16,14,10,8,7,9,3}建立一个最大堆,应从哪个节点开始出发做hea

如果要将二叉树{16,14,10,8,7,9,3}建立一个最大堆,应从哪个节点开始出发做hea

给定一个非空二叉树,返回其最大路径和。

本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。、

思路:
这道题,首先要正确理解题目意思。返回一个最大路径和,很容易想到用递归地方法,将子节点的路径和求出,加上自身就是该节点为根的路径和。题目的要求是从任意节点出发,而不是子树的根节点出发,因此要将左右子树的路径和都加上才符合题意。
当然,计算中需要判断左右子树路径和加自身节点值是否变小(也就是子树路径小于0)

	int sum_max =INT_MIN;
    int maxPathSum(TreeNode* root) {
        int ans = 0;

        //深先用优先搜索吧
        dfs(root);
        return sum_max;
    }

    int dfs(TreeNode* node)
    {

        if(node == nullptr)
        {
            return 0;
        }
        int val = node->val;
        int sum_left = dfs(node->left);
        int sum_right = dfs(node->right);
        int sum_all = val+sum_left+sum_right;

        val = max(max(val+sum_left, val + sum_right), val);
        int sum = max(val, sum_all);

        sum_max = max(sum, sum_max);
        return val;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/943755
推荐阅读
相关标签
  

闽ICP备14008679号