未分類

Path Sum

DepthFirstSearch, Go, LeetCode, Modify, Tree

Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:

Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

提示 解題應用
Tree 樹的遍歷方式
DepthFirstSearch PostOrderTravel

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 hasPathSum(root *TreeNode, sum int) bool {
}

解答思路:

(此題思路有修正，建議看完直接拉到最底下參考修正的部分)

與尋找二元樹的最小深度一樣，要注意的是一定要從存在的樹根到樹末(樹葉)來尋找，所以會發生只到中間的節點符合條件，反而往其子節點走就不符合條件，對於那些nil節點一樣要做些處理以免誤判，nil節點我回傳了一個32位元int的極大值，如果其一節點的兩個左右子節點都回傳極大值，如此一來便知道已經到達了樹葉節點，此時在判斷節點總合是否符合目標值，其餘的節點若有任一左右子節點就繼續遞回做後序遍歷，而不符合目標值的路徑則回傳一個極小值，與符合條件的任一值以此區分空節點、不符合的路徑、符合的路徑。

程式碼解說:

這邊一開始先判斷節點是否存在，不存在就回傳一個極大值，接著便分左右子節點來做遞回，而至於是否於目標值相符，這邊我將目標值與路徑上的節點做相減，當結果為0且回傳的左右子節點皆為極大值，表示存在著符合條件的路徑以回傳0來表示，不過因為在向上回傳的過程中，節點會碰上像是左子樹的路徑符合，而另一右子樹則無，此時只要其一路徑符合就繼續向上回傳0，最後不符合的路徑就回傳極小值來區別

1
2
3
4
5
6
7
8
9
10
11
12
13
var sumL int
var sumR int
if node == nil {
	return math.MaxInt32
}
sumL = postOrderTravel(node.Left, sum-node.Val)
sumR = postOrderTravel(node.Right, sum-node.Val)
if sum-node.Val == 0 && sumL == math.MaxInt32 && sumR == math.MaxInt32 {
	return 0
} else if sumL == 0 || sumR == 0 {
	return 0
}
return math.MinInt32

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func hasPathSum(root *TreeNode, sum int) bool {
	result := postOrderTravel(root, sum)
	if result == 0 {
		return true
	}
	return false
}
func postOrderTravel(node *TreeNode, sum int) int {
	var sumL int
	var sumR int
	if node == nil {
		return math.MaxInt32
	}
	sumL = postOrderTravel(node.Left, sum-node.Val)
	sumR = postOrderTravel(node.Right, sum-node.Val)
	if sum-node.Val == 0 && sumL == math.MaxInt32 && sumR == math.MaxInt32 {
		return 0
	} else if sumL == 0 || sumR == 0 {
		return 0
	}
	return math.MinInt32
}

總結:

在二元樹中尋找特定的路徑(從樹根到樹葉)，像是二元樹的最短路徑與節點總合，都是一定要是從根到葉的完整路徑，就算僅到中間的節點便符合條件，只要該節點仍有任一子節點就一定要往下走，很容易因為這樣而將原本不符合條件的結果回傳成符合條件的結果。

二元樹路徑上的節點值總合是否存在符合目標值，首先要注意nil節點回傳極大值以避免上述情況，當左右子節點回傳皆為極大值時，便能知道已經到達樹葉節點，此時在判斷總合是否相符，而對於最終總合不符的樹節點，再往上回傳極小值，以此來區分:

  • 不符合條件的路徑(極小值)

  • 空節點(極大值)

  • 符合條件的路徑(任一值)

修正

主要是不需要用極大值、極小值的方式判斷路徑，直接從節點判斷左右子節點是否存在，再考慮需不需要遍歷該子節點，如此一來就可以省去非常多的麻煩，大多數關於樹的遍歷都可以用此方式處理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func hasPathSum(root *TreeNode, sum int) bool {
	if root == nil {
		return false
	}
	return preOrderTravel(root, sum)
}
func preOrderTravel(node *TreeNode, sum int) bool {
	if node.Left == nil && node.Right == nil {
		if sum-node.Val == 0 {
			return true
		}
		return false
	} else if node.Left == nil {
		return preOrderTravel(node.Right, sum-node.Val)
	} else if node.Right == nil {
		return preOrderTravel(node.Left, sum-node.Val)
	}
	return preOrderTravel(node.Left, sum-node.Val) || preOrderTravel(node.Right, sum-node.Val)
}
分享到