未分類

Binary Tree Paths

DepthFirstSearch, Go, LeetCode, Tree

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...)
}

總結:

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

分享到