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 负责计算子树上的可能路径的和。

很多时候简洁 = 正确。

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