未分類

Path Sum II

DepthFirstSearch, Go, LeetCode, Tree

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum 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  5   1

return

1
2
3
4
[
   [5,4,11,2],
   [5,8,4,5]
]
提示 解題應用
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 pathSum(root *TreeNode, sum int) [][]int {
}

解答思路:

建議可以先參考先前Path Sum的解法，解說較為詳細，基本上概念完全一樣，只是將先前題的程式碼稍做修改而已，如果能找出有多少條根到葉子的路徑能符合目標總合，當然這次要列出所有的路徑就不會太困難。

主要也是直接從節點判斷左右子節點是否存在，再考慮需不需要遍歷該子節點，並同時記錄一路上經過的節點值，最後如果需要遍歷子節點時，將已記錄的路徑再次帶入遞回之中直到路徑符合目標總合為止才向上回傳。

程式碼解說:

一開始先判斷根節點是否存在，如果連根節點都不存在就直接回傳一個空的二元陣列，而如果根節點存在則將其帶入遞回函數之中，其中第三個參數是用來記錄已遍歷的節點值

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

再來就是處理遞回的細節，先將目前的節點值記錄到路徑之中，接著判斷左右子節點是否存在，如果兩邊子節點都不存在表示已經到了最尾端的葉子節點，這時就再檢查最後目前總合是否歸0(表示路徑總合符合目標值)，如果是就將此路徑向上回傳(因為slice的特性，這邊要複製到新的陣列再回傳)，如果路徑到底了與目標值不相符則回傳空的路徑回去，至於如果左右子節點任一邊存在就遞回遍歷、記錄那一邊的路徑，兩邊子節點都存在就兩邊都遍歷，只是最後回傳時要記得將兩邊的結果路徑合併才向上回傳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func preOrderTravel(node *TreeNode, sum int, tmp []int) [][]int {
    tmp = append(tmp, node.Val)
	if node.Left == nil && node.Right == nil {
	    if sum - node.Val == 0 {
	        result := make([]int, len(tmp))
            copy(result, tmp)
	        return [][]int{result}
	    }
	    return [][]int{}
	}else if node.Left == nil {
	    return preOrderTravel(node.Right, sum-node.Val, tmp)
	}else if node.Right == nil {
	    return preOrderTravel(node.Left, sum-node.Val, tmp)
	}
	left := preOrderTravel(node.Left, sum-node.Val, tmp)
	right := preOrderTravel(node.Right, sum-node.Val, tmp)
	return append(left, right...)
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func pathSum(root *TreeNode, sum int) [][]int {
    if root == nil {
        return [][]int{}
    }
    return preOrderTravel(root, sum, []int{})
}
func preOrderTravel(node *TreeNode, sum int, tmp []int) [][]int {
    tmp = append(tmp, node.Val)
	if node.Left == nil && node.Right == nil {
	    if sum - node.Val == 0 {
	        result := make([]int, len(tmp))
            copy(result, tmp)
	        return [][]int{result}
	    }
	    return [][]int{}
	}else if node.Left == nil {
	    return preOrderTravel(node.Right, sum-node.Val, tmp)
	}else if node.Right == nil {
	    return preOrderTravel(node.Left, sum-node.Val, tmp)
	}
	left := preOrderTravel(node.Left, sum-node.Val, tmp)
	right := preOrderTravel(node.Right, sum-node.Val, tmp)
	return append(left, right...)
}

總結:

建議可以先參考先前Path Sum的解法，解說較為詳細，基本上概念完全一樣，這次只是要從紀錄符合條件的路徑數改為列出所有的路徑，主要也是直接從節點判斷左右子節點是否存在，再考慮需不需要遍歷該子節點，並同時記錄一路上經過的節點值，最後如果需要遍歷子節點時，將已記錄的路徑再次帶入遞回之中直到路徑符合目標總合為止才向上回傳。

分享到