美文网首页
binary-tree-maximum-path-sum

binary-tree-maximum-path-sum

作者: DaiMorph | 来源:发表于2019-06-09 00:24 被阅读0次

    首先我们分析一下对于指定某个节点为根时,最大的路径和有可能是哪些情况:

    第一种是左子树的路径加上当前节点,

    第二种是右子树的路径加上当前节点,

    第三种是左右子树的路径加上当前节点(相当于一条横跨当前节点的路径),

    第四种是只有自己的路径。

    乍一看似乎以此为条件进行自下而上递归就行了,然而这四种情况只是

    用来计算以当前节点根的最大路径,如果当前节点上面还有节点,

    那它的父节点是不能累加第三种情况的。所以我们要计算两个最大值,

    一个是当前节点下最大路径和,另一个是如果要连接父节点时最大的路径和。

    我们用前者更新全局最大量,用后者返回递归值就行了。

    * 算法的本质还是一次树的遍历,所以复杂度是O(n)。而空间上仍然是栈大小O(logn)。

    class Solution {
    public:
        int res=INT_MIN;
        int maxPathSum(TreeNode *root) {
            dfs(root);
            return res;
        }
        int dfs(TreeNode*root){
            if(root==NULL)return 0;
            int l=max(0,dfs(root->left));
            int r=max(0,dfs(root->right));
            res=max(res,root->val+l+r);
            return root->val+max(l,r);
        }
    };
    

    相关文章

      网友评论

          本文标题:binary-tree-maximum-path-sum

          本文链接:https://www.haomeiwen.com/subject/dbzwxctx.html