未分類

Binary Tree Level Order Traversal II

BreadthFirstSearch, Go, LeetCode, Tree

Binary Tree Level Order Traversal II

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

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

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

return its bottom-up level order traversal as:

1
2
3
4
5
[
  [15,7],
  [9,20],
  [3]
]
提示 解題應用
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 levelOrderBottom(root *TreeNode) [][]int {
}

解答思路:

此題和先前文章的Binary Tree Level Order Traversal思路太過類似所以內容就大部分照貼，雖然你可以直接拿該題程式照貼，不過最後還會要多一步將結果反轉，與其這樣倒不如一開始就將每一列陣列往開頭插入，而且修改的部分也只有一點點。

很明顯的是要使用廣度優先遍歷的方式來遍歷整棵二元樹，雖然不一定是完全二元樹，不過既然最後一列要在最前頭，這意味著每次二元樹的每一列要將新的陣列差插入結果時，一定是在最前面，也就是index為0的位置，這讓我們省去了找哪個節點是在哪一列的問題，因為一定是往index為0的陣列放，不過列的位數還是要存著，因為仍不曉得什麼時候要將值插入index為0的陣列或是要在原本index為0的位置放入新陣列。

程式碼解說:

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

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

將根節點放入隊列中，同時也將列的位數也儲存起來，這邊從0開始做第n列的起頭，方便我們知道什麼時候該再往index為0的位置放入新陣列

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

在開頭依舊是利用結果的長度(有幾個陣列)來與節點的列數做比較，如果節點已經到下一列了而陣列數量還沒準備給下一列的值塞入，這時就需要產生一個新的陣列包含該節點的值在最前面，然後在把原本的結果依序從其後頭插入，至於那些不是每一列第一個的節點，只管往index為0的陣列塞就對了，因為每一列新插入的值一定都在最前面的陣列，而最後只要判斷節點左右的子節點存不存在依序插入隊列就完成了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
for front != nil {
	if len(result) < front.Row+1 {
		result = append([][]int{[]int{front.Node.Val}}, result...)
	} else {
		result[0] = append(result[0], 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
type QueneNode struct {
	Row  int
	Node *TreeNode
	Next *QueneNode
}
func levelOrderBottom(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([][]int{[]int{front.Node.Val}}, result...)
		} else {
			result[0] = append(result[0], 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
}

總結:

碰上二元樹要做廣度優先遍歷，然後結果卻要相反的儲存，不妨先將依序做儲存的結果給實作出來，如此一來便能很輕易的修改成相反儲存的結果。

分享到