未分類

Binary Tree Paths

Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

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

All root-to-leaf paths are:

1
["1->2->5", "1->3"]
提示 解題應用
Tree Pointer
DepthFirstSearch PreOrderTravel

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 binaryTreePaths(root *TreeNode) []string {
}

解答思路:

列出一二元樹的特定路徑時,正如尋找最大深度所會碰上的問題一樣,在做前序遍歷時需要對那些左右子節點是否存在做處理,尤其是左或右子節點僅其中一點存在的情況下,容易將另一不存在的子節點當作終點作為其路徑,以上述例子來說存在著”1->2->5”,然而2的左子節點不存在,但”1->2”並非是能到達的最大路徑(深度),這邊僅需要藉由其子節點存在的判斷來決定是否遍歷,便能輕易回避此問題取得所需的結果。

程式碼解說:

一開始先確定根節點是否為nil,如果是就回傳空的字串陣列,否則才開始前序遍歷遞回每一個節點

1
2
3
4
5
6
func binaryTreePaths(root *TreeNode) []string {
if root == nil {
return []string{}
}
return preOrderTravel(root, "")
}

如果節點的左右子節點都不存在,就表示已經來到了路徑的末端,這時只要將該節點的值附上,在帶入字串陣列中回傳即可,而如果是有子節點存在的情況就記得在字串的後頭加上”->”,正如先前所說我們藉由其子節點存在的判斷來決定是否遍歷,如果左子節點不存在就遍歷右子節點,如果右子節點不存在則遍歷左子節點,最後如果兩個子節點皆存在,等到兩子節點遞回結果後,才將兩字串陣列做合併向上回傳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func preOrderTravel(node *TreeNode, path string) []string {
if node.Left == nil && node.Right == nil {
path = path + strconv.Itoa(node.Val)
return []string{path}
}
path = path + strconv.Itoa(node.Val) + "->"
if node.Left == nil {
return preOrderTravel(node.Right, path)
}
if node.Right == nil {
return preOrderTravel(node.Left, path)
}
leftPath := preOrderTravel(node.Left, path)
rightPath := preOrderTravel(node.Right, path)
return append(leftPath, rightPath...)
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func binaryTreePaths(root *TreeNode) []string {
if root == nil {
return []string{}
}
return preOrderTravel(root, "")
}
func preOrderTravel(node *TreeNode, path string) []string {
if node.Left == nil && node.Right == nil {
path = path + strconv.Itoa(node.Val)
return []string{path}
}
path = path + strconv.Itoa(node.Val) + "->"
if node.Left == nil {
return preOrderTravel(node.Right, path)
}
if node.Right == nil {
return preOrderTravel(node.Left, path)
}
leftPath := preOrderTravel(node.Left, path)
rightPath := preOrderTravel(node.Right, path)
return append(leftPath, rightPath...)
}

總結:

列出一二元樹的特定路徑時,前序遍歷時需要對那些左右子節點是否存在做處理,尤其是左或右子節點僅其中一點存在的情況下,容易將另一不存在的子節點當作終點作為其路徑,因此藉由其子節點存在的判斷來決定是否遍歷,便能輕易回避此問題取得所需的結果。

分享到