未分類

House Robber III

DepthFirstSearch, Go, LeetCode, Tree

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
}

總結:

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

分享到