未分類

House Robber III

House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

1
2
3
4
5
3
/ \
2 3
\ \
3 1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

1
2
3
4
5
3
/ \
4 5
/ \ \
1 3 1

Maximum amount of money the thief can rob = 4 + 5 = 9.

提示 解題應用
DepthFirstSearch 樹的遍歷

Default:

1
2
3
4
5
6
7
8
9
10
11
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rob(root *TreeNode) int {
}

解答思路:

剛看到題目時很容易因為範例而被誤導使用廣度優先遍歷,求出每列的總合再做組合找最大值,然而仔細看題目的話只要不是連偷兩間屋子,也就是節點跟子節點連續就不會有問題,所以節點的左子樹與右子樹間是互相獨立的,因此在做樹的遞回遍歷時,只要比較”該節點+左子節點的子樹(左右子樹)遞回結果+右子節點的子樹(左右子樹)遞回結果”與”左子樹的遞回結果+右子樹的遞回結果”兩個值誰大再向上回傳即可,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func rob(root *TreeNode) int {
if root == nil {
return 0
}
var tmp int
if root.Left != nil {
tmp += rob(root.Left.Left) + rob(root.Left.Right)
}
if root.Right != nil {
tmp += rob(root.Right.Left) + rob(root.Right.Right)
}
return max(tmp+root.Val, rob(root.Left)+rob(root.Right))
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}

不難發現到在遞回節點子樹的最大結果時,與另一個遞回節點子樹的子樹似乎有重覆遞回的情況,這將導致花費時間大幅度的上升,因此針對這種情況只要把遞回修改成每次都回傳兩個值,包含該節點的最大結果與不包含該節點的最大結果,剩下的工作交由上一層去組合並比較大小,就能只經由遞回遍歷各節點一次找出最終的最大竊取金額。

程式碼解說:

一開始就將根節點帶入遞回函數之中,接著只要比較回傳的”包含根節點的最大結果”與”不包含根節點的最大結果”誰比較大,其值就會是最終能竊取的最大金額

1
2
3
4
func rob(root *TreeNode) int {
in, ex := dfs(root)
return max(in, ex)
}

至於遞回函數的細節,如果帶入的節點為空就回傳兩個0(因為遞回每次都會回傳兩個值),否則就分別將左右子節點再次帶入遞回函數之中,最後向上回傳包含該節點的最大結果(該節點+左子節點的子樹遞回結果[不包含左子節點]+右子節點的子樹遞回結果[不包含右子節點])與不包含該節點的最大結果(左子樹的遞回結果[從包含/不包含左子節點中取較大的值]+右子樹的遞回結果[從包含/不包含右子節點中取較大的值])即可

1
2
3
4
5
6
7
8
func dfs(node *TreeNode) (int, int) {
if node == nil {
return 0, 0
}
inL, exL := dfs(node.Left)
inR, exR := dfs(node.Right)
return node.Val + exL + exR, max(inL, exL) + max(inR, exR)
}

這部分的函數就只是單純比較哪個值最大,並向上回傳比較大的那一個值

1
2
3
4
5
6
func max(a int, b int) int {
if a > b {
return a
}
return b
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func rob(root *TreeNode) int {
in, ex := dfs(root)
return max(in, ex)
}
func dfs(node *TreeNode) (int, int) {
if node == nil {
return 0, 0
}
inL, exL := dfs(node.Left)
inR, exR := dfs(node.Right)
return node.Val + exL + exR, max(inL, exL) + max(inR, exR)
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}

總結:

二元樹其每個節點分別代表一間屋子,而節點值則是屋子所擁有的現金,要竊取最大金額而不觸發警報(不連偷兩間屋子,也就是節點跟子節點連續),做法是在進行樹的遞回遍歷時,只要比較”該節點+左子節點的子樹(左右子樹)遞回結果+右子節點的子樹(左右子樹)遞回結果”與”左子樹的遞回結果+右子樹的遞回結果”兩個值誰大再向上回傳即可,然而在遞回節點子樹的最大結果時,與另一個遞回節點子樹的子樹似乎有重覆遞回的情況,這將導致花費時間大幅度的上升,因此針對這種情況只要把遞回修改成每次都回傳兩個值,包含該節點的最大結果與不包含該節點的最大結果,剩下的工作交由上一層去組合並比較大小,就能只經由遞回遍歷各節點一次找出最終的最大竊取金額。

分享到