叶到根的最大总和

Question

给定一棵二叉树，找到从叶子到根的最大和路径。 https://practice.geeksforgeeks.org/problems/maximum-sum-leaf-to-root-path/1

class Solution:
    def maxPathSum(self, root):
        #code here
        maxi = float('-inf')
        def dfs(cur,cursum):
            nonlocal maxi
            if not cur : return 
            if not cur.left and not cur.right:
                maxi = max(maxi,cur.data + cursum)
                return 
            cursum += cur.data
            dfs(cur.left,cursum)
            cursum -= cur.data
            dfs(cur.right,cursum)
        dfs(root,0)
        return maxi 

我尝试了上面的代码，考虑到累积和（cursum）是通过在遍历其左右子节点之前添加当前节点的数据来更新的。遍历完子节点后，通过减去当前节点的数据来恢复累积和

但是解决方案不起作用

class Solution:
    def maxPathSum(self, root):
        #code here
        maxi = float('-inf')
        def dfs(cur,cursum):
            nonlocal maxi
            if not cur : return 
            if not cur.left and not cur.right:
                maxi = max(maxi,cur.data + cursum)
                return 
            cursum += cur.data
            dfs(cur.left,cursum)
            cursum -= cur.data
            dfs(cur.right,cursum)
        dfs(root,0)
        return maxi 

我尝试了上面的代码，考虑到累积和（cursum）是通过在遍历其左右子节点之前添加当前节点的数据来更新的。遍历完子节点后，通过减去当前节点的数据来恢复累积和

但是解决方案不起作用

Answer 1

遍历完子节点后，通过减去当前节点的数据来恢复累加和

这是正确的想法，但你没有正确执行。问题是您还需要包含

cur.data

才能遍历 right 子树。所以你做减法太早了。

改变：

        cursum += cur.data
        dfs(cur.left,cursum)
        cursum -= cur.data
        dfs(cur.right,cursum)

至：

        cursum += cur.data
        dfs(cur.left,cursum)
        dfs(cur.right,cursum)
        cursum -= cur.data     # <--- moved

现在就可以了。您甚至可以避免更改

cursum

变量，而只需将 表达式 作为参数传递给递归调用：

        dfs(cur.left,cursum + cur.data)
        dfs(cur.right,cursum + cur.data)