Lever's Castle

437. 路径总和 III

March 23, 2019

https://leetcode-cn.com/problems/pa-sum-iii/

使用语言 Golang

先上正确的解决方案:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumChild(root *TreeNode, sum int) int {
    if root == nil {
        return 0
    }
    
    r := 0
    if root.Val == sum {
        r = 1
    }
    
    newSum := sum - root.Val
    return r + sumChild(root.Left, newSum) + sumChild(root.Right, newSum)
}
func pathSum(root *TreeNode, sum int) int {
    if root == nil {
        return 0
    }
    return sumChild(root, sum) + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}

感悟:思路正确的程序,一定是最简洁直观的。

其实我最开始的思路就一直很正确,我把问题分解了一下,实际上就是求每个路径的和,其中和等于目标值的次数。下面是我第一次的提交:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumChild(root *TreeNode, targetSum int, sum int) int {
        if root == nil {
        return 0
    }
    if root.Val == sum {
        return 1 + sumChild(root.Left, targetSum, targetSum) + sumChild(root.Right, targetSum, targetSum)
    } else if root.Val > sum {
        return 0 + sumChild(root.Left, targetSum, targetSum) + sumChild(root.Right, targetSum, targetSum)
    }
    
    newSum := sum - root.Val
    return sumChild(root.Left, targetSum, newSum) + sumChild(root.Right, targetSum, newSum) + sumChild(root.Left, targetSum, sum) + sumChild(root.Right, targetSum, sum)
}
func pathSum(root *TreeNode, sum int) int {
    return sumChild(root, sum, sum)
}

sumChild 的逻辑比较复杂,除了判断边界,我还判断了当前值与目标值的差异,这样其实是有问题的:并不是当前值比目标值大,就意味着整条路径都没有希望了。我也是在测试用例跑挂之后才想明白这个问题。

改了一版变成了这样:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumChild(root *TreeNode, targetSum int, sum int) int {
    if root == nil {
        return 0
    }
    if root.Val == sum {
        return 1 + sumChild(root.Left, targetSum, targetSum) + sumChild(root.Right, targetSum, targetSum)
    }
    
    newSum := sum - root.Val
    return sumChild(root.Left, targetSum, newSum) + sumChild(root.Right, targetSum, newSum) + sumChild(root.Left, targetSum, targetSum) + sumChild(root.Right, targetSum, targetSum)
}
func pathSum(root *TreeNode, sum int) int {
    return sumChild(root, sum, sum)
}

这回只针对等值的情况做了处理,然而测试用例依然没跑过,挂在了下面这个输入上:

[1,null,2,null,3,null,4,null,5]
3

期望结果是 2,但是我跑出来是 3。想了想之后,我明白了: 我的程序中发生了重复遍历!

就是同一条路径,遍历了多次。

很明显,我为了确保能够遍历到每一条路径,在 sumChild 中故意留了一个 targetSum,并用这个 targetSum 向每个子树进行递归。但实际上 sumChild 自己也在递归。拿左子树举个例子,左子树用新值递归了一遍,又用真实的目标值递归了一遍,对于左子树的左子树来讲,他一定会被递归到两次。

我忽然意识到,targetSum 这样一个很变扭的东西或许本身就不该出现,当你觉得一个东西很变扭的时候,可能他真的有问题。思考之后,我把程序改成了这样:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumChild(root *TreeNode, sum int) int {
    if root == nil {
        return 0
    }
    
    r := 0
    if root.Val == sum {
        r = 1
    }
    
    newSum := sum - root.Val
    return r + sumChild(root.Left, newSum) + sumChild(root.Right, newSum)
}
func pathSum(root *TreeNode, sum int) int {
    if root == nil {
        return 0
    }
    return sumChild(root, sum) + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}

整个程序变的豁然开朗,pathSum 负责遍历每个子树,而 sumChild 负责计算子树上的可能路径的和。

很多时候 简洁 = 正确。


Lever

痕迹
没有过去,就没法认定现在的自己