未分類

Path Sum III

Go, LeetCode, Tree

Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

For Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
Return 3. The paths that sum to 8 are:
1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11
提示 解題應用
Tree 前序遍歷

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

解答思路:

這題最大的麻煩在於任一個點都可以成為起始點，此外若有某條路徑已經達到目標總合，仍需繼續往下做判斷，因為還是有可能再次達到目標總合，這時又算是另外符合條件的路徑，既然不曉得哪些點為起始時能達到目標總合，只好將所有的點都當作起始點來尋找，也就是每個節點與其以下的子節點都再當作一顆獨立的樹來遍歷，再找出以該節點為根節點開始路徑的所有可能，因此總共需要兩次遍歷，一次遍歷所有的節點，另一次則是遍歷以該節點為根節點的樹並從其開始的所有路徑，最後再將每個獨立樹找出的所有路徑再全部做總合就是我們的結果。

程式碼解說:

一開始先檢查樹的根節點是否存在，若不存在則回傳0，接著才開始遍歷所有節點

1
2
3
4
5
6
func pathSum(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}
	return preOrderTravel(root, sum, 0)
}

第一次的前序遍歷是要將樹所有的節點當作根節點作為獨立的小樹，treeSum的function是我們為小樹做第二次前序遍歷，並將該小樹的所有可能回傳，若左右子節點為空表示沒有其它能再次遍歷的小樹，因此直接回傳目前符合條件的路徑數，如果有左右任一子節點為空，則遍歷另一側的子節點生成小樹，最後若左右子節點皆不為空，遍歷兩側節點並生成兩邊小樹，這裡要注意的是因為符合條件的路徑數是由上往下累加，如果將累加數同時帶入左右兩邊會造成重覆計算，所以只要挑其中一邊繼續累加，另一邊則從頭開始算

1
2
3
4
5
6
7
8
9
10
11
func preOrderTravel(node *TreeNode, sum int, count int) int {
	count += treeSum(node, sum, 0)
	if node.Left == nil && node.Right == nil {
		return count
	} else if node.Left == nil {
		return preOrderTravel(node.Right, sum, count)
	} else if node.Right == nil {
		return preOrderTravel(node.Left, sum, count)
	}
	return preOrderTravel(node.Left, sum, count) + preOrderTravel(node.Right, sum, 0)
}

再來第二次的前序遍歷則是遍歷每個節點為根節點所生成小樹，並計算所有可能，總合與路徑節點值相減歸0，表示該路徑符合條件，此時將路徑數+1但不要回傳，仍要繼續往下確定同一路徑到葉節點是否還存在其它符合條件的可能，如果左右子節點為空，此時才可以放心回傳路徑數，而如果左右任一為空則往另一則繼續判斷其它路徑的可能性，最後如果左右子節點都不為空，則都要繼續遍歷並判斷所有可能，而與前一次遍歷一樣的狀況，如果將累加數同時帶入左右兩邊會造成重覆計算，所以也是挑其中一邊繼續累加，另一邊則從頭開始算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func treeSum(node *TreeNode, sum int, count int) int {
	tmp := sum - node.Val
	if tmp == 0 {
		count++
	}
	if node.Left == nil && node.Right == nil {
		return count
	} else if node.Left == nil {
		return treeSum(node.Right, tmp, count)
	} else if node.Right == nil {
		return treeSum(node.Left, tmp, count)
	}
	return treeSum(node.Left, tmp, count) + treeSum(node.Right, tmp, 0)
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func pathSum(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}
	return preOrderTravel(root, sum, 0)
}
func preOrderTravel(node *TreeNode, sum int, count int) int {
	count += treeSum(node, sum, 0)
	if node.Left == nil && node.Right == nil {
		return count
	} else if node.Left == nil {
		return preOrderTravel(node.Right, sum, count)
	} else if node.Right == nil {
		return preOrderTravel(node.Left, sum, count)
	}
	return preOrderTravel(node.Left, sum, count) + preOrderTravel(node.Right, sum, 0)
}
func treeSum(node *TreeNode, sum int, count int) int {
	tmp := sum - node.Val
	if tmp == 0 {
		count++
	}
	if node.Left == nil && node.Right == nil {
		return count
	} else if node.Left == nil {
		return treeSum(node.Right, tmp, count)
	} else if node.Right == nil {
		return treeSum(node.Left, tmp, count)
	}
	return treeSum(node.Left, tmp, count) + treeSum(node.Right, tmp, 0)
}

總結:

若有一顆二元樹，其所有節點都能做為根節點，且達目標總合時不需於葉子節點結束，找出所有的路徑，而最大的麻煩在於任一個點都可以成為起始點，此外若有某條路徑已經達到目標總合，仍需繼續往下做判斷，因為還是有可能再次達到目標總合，這時又算是另外符合條件的路徑，因此總共需要兩次遍歷，一次遍歷所有的節點，另一次則是遍歷以該節點為根節點的樹並從其開始的所有路徑，最後再將每個獨立樹找出的所有路徑再全部做總合就是我們的結果。

分享到