437. 路徑總和 III
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 負責計運算元樹上的可能路徑的和。
很多時候 簡潔 = 正確。