未分類

Binary Tree Level Order Traversal

BreadthFirstSearch, Go, LeetCode, Tree

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its level order traversal as:

1
2
3
4
5
[
  [3],
  [9,20],
  [15,7]
]
提示 解題應用
Tree 樹的遍歷方式
BreadthFirstSearch Quene

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

解答思路:

很明顯的是要使用廣度優先遍歷的方式來遍歷整棵二元樹，只是因為不一定是完全二元樹，所以不能用計算的方式來記錄要存到第幾個陣列，那麼就只好將該列的位數與節點一起儲存，並且當其左右子節點要進入隊列時將列的位數+1就可以了，如此以來在取出的時候就可以知道要存入哪個陣列(其實就是結果的最後一個陣列)。

程式碼解說:

這邊我是用LinkedList的方式來實現隊列，當然也可以用陣列的方式來實現，作法因人而異

1
2
3
4
5
type QueneNode struct {
	Row  int
	Node *TreeNode
	Next *QueneNode
}

將根節點放入隊列中，同時也將列的位數也儲存起來，這邊從0開始做第n列的起頭，方便我們等等在存入index值時就可以直接使用

1
2
3
4
5
6
7
8
9
10
var row int
var tmp *QueneNode
var front *QueneNode
var rear *QueneNode
tmp = &QueneNode{}
tmp.Node = root
tmp.Row = row
front = tmp
rear = tmp

因為在遍歷的過程中如果已經有該列的陣列，那麼直接將數字插入即可，但如果沒有也就是說是該列的第一個，這時就需要初始化一個新的slice，這邊我是直接將一個新的陣列連同值一起做插入，而最後只要判斷左右的子節點存不存在依序插入隊列就完成了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for front != nil {
	if len(result) < front.Row+1 {
		result = append(result, []int{front.Node.Val})
	} else {
		result[front.Row] = append(result[front.Row], front.Node.Val)
		//result[len(result)-1] = append(result[len(result)-1], front.Node.Val)
	}
	if front.Node.Left != nil {
		tmp = &QueneNode{}
		tmp.Node = front.Node.Left
		tmp.Row = front.Row + 1
		rear.Next = tmp
		rear = tmp
	}
	if front.Node.Right != nil {
		tmp = &QueneNode{}
		tmp.Node = front.Node.Right
		tmp.Row = front.Row + 1
		rear.Next = tmp
		rear = tmp
	}
	front = front.Next
}
return result

完整程式碼:

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
32
33
34
35
36
37
38
39
40
41
42
43
44
type QueneNode struct {
	Row  int
	Node *TreeNode
	Next *QueneNode
}
func levelOrder(root *TreeNode) [][]int {
	var result [][]int
	if root == nil {
		return result
	}
	var row int
	var tmp *QueneNode
	var front *QueneNode
	var rear *QueneNode
	tmp = &QueneNode{}
	tmp.Node = root
	tmp.Row = row
	front = tmp
	rear = tmp
	for front != nil {
		if len(result) < front.Row+1 {
			result = append(result, []int{front.Node.Val})
		} else {
			result[front.Row] = append(result[front.Row], front.Node.Val)
			//result[len(result)-1] = append(result[len(result)-1], front.Node.Val)
		}
		if front.Node.Left != nil {
			tmp = &QueneNode{}
			tmp.Node = front.Node.Left
			tmp.Row = front.Row + 1
			rear.Next = tmp
			rear = tmp
		}
		if front.Node.Right != nil {
			tmp = &QueneNode{}
			tmp.Node = front.Node.Right
			tmp.Row = front.Row + 1
			rear.Next = tmp
			rear = tmp
		}
		front = front.Next
	}
	return result
}

總結:

如果要記錄二元樹遍歷的每列橫排數字，那除了要用廣度優先遍歷來做之外，也別忘記一併記下每一個節點是在哪一列的位置，如此一來其子節點只要在放入隊列前依尋這個父節點的列位置+1，在取出時就可以知道該節點是第幾列了。

分享到