未分類

Binary Tree Zigzag Level Order Traversal

BreadthFirstSearch, Go, LeetCode, Stack, Tree

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:

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

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

return its zigzag level order traversal as:

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

解答思路:

原本的想法是在做廣度優先遍歷時，在將節點放入隊列時原本是先放左節點再放右節點，到了下一列改成先放右節點再放左節點，但最後出來的節點順序會發現不太對，其實根本就不需要這麼麻煩，換一個角度來想只要照常做原本的廣度優先遍歷就好，最後只要在做儲存結果時改變儲存的順序就搞定了，從原本依序放入結果陣列後頭，到下一列就改為依序放入結果陣列的開頭，至於放入隊列後要如何知道每個節點原本是位在哪一列，只要隊列的結構再多儲存一個列數的參數就好，如此一來不但能知道哪幾列要將值依序放入結果陣列的後頭還前頭，也能透過列數來確定要放的結果陣列是二元陣列中的哪一列。

程式碼解說:

既然要做廣度優先遍歷，一開始當然就先定義好隊列儲存LinkedList的結構，而為了要在節點放入後也能知道該節點的列數，隊列的結構還要再多儲存一個列數的參數

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

接下來就是實作遍歷的細節，一開始先將根節點放入隊列之中(參數分別為列數,節點位置,下一個隊列節點位置)，並以兩個指標來指向隊列的開頭與結尾，接著就是以迴圈不斷遍歷隊列的節點直到隊列為空為止，如果用結果二元陣列中有用來存放該節點列數的陣列(二元陣列中的陣列數大於等於節點的列數)，就再判斷節點的列數是否為2的倍數，如果是就將節點值放入對應列數陣列的開頭，而如果不是2的倍數則將節點值放入對應列數陣列的後頭，至於如果結果二元陣列中沒有用來存放該節點列數的陣列，表示要新增一個對應列數的陣列到二元陣列之中，此時節點值又是新增對應列數陣列的第一個值，所以就直接放進去沒有前後之分，最後待隊列開頭的節點存取完畢後，後續的過程就是正常的廣度優先遍歷，如果左或右子節點存在就將其放入隊列的後頭並移動隊列結尾指標到最後頭，確定將左或右子節點放入隊列之後才再把隊列開頭指標移到下一個

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
func zigzagLevelOrder(root *TreeNode) [][]int {
	var result [][]int
	front := &QueneNode{1, root, nil}
	rear := front
	for front != nil && front.Node != nil {
		if len(result) >= front.Row {
			if front.Row%2 == 0 {
				result[front.Row-1] = append([]int{front.Node.Val}, result[front.Row-1]...)
			} else {
				result[front.Row-1] = append(result[front.Row-1], front.Node.Val)
			}
		} else {
			result = append(result, []int{front.Node.Val})
		}
		if front.Node.Left != nil {
			rear.Next = &QueneNode{front.Row + 1, front.Node.Left, nil}
			rear = rear.Next
		}
		if front.Node.Right != nil {
			rear.Next = &QueneNode{front.Row + 1, front.Node.Right, nil}
			rear = rear.Next
		}
		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
type QueneNode struct {
	Row  int
	Node *TreeNode
	Next *QueneNode
}
func zigzagLevelOrder(root *TreeNode) [][]int {
	var result [][]int
	front := &QueneNode{1, root, nil}
	rear := front
	for front != nil && front.Node != nil {
		if len(result) >= front.Row {
			if front.Row%2 == 0 {
				result[front.Row-1] = append([]int{front.Node.Val}, result[front.Row-1]...)
			} else {
				result[front.Row-1] = append(result[front.Row-1], front.Node.Val)
			}
		} else {
			result = append(result, []int{front.Node.Val})
		}
		if front.Node.Left != nil {
			rear.Next = &QueneNode{front.Row + 1, front.Node.Left, nil}
			rear = rear.Next
		}
		if front.Node.Right != nil {
			rear.Next = &QueneNode{front.Row + 1, front.Node.Right, nil}
			rear = rear.Next
		}
		front = front.Next
	}
	return result
}

總結:

如果要將二元樹以鋸齒狀的方式來遍歷(同一層的節點先由左遍歷至右，到下一層再由右遍歷至左)，只要先照常做原本的廣度優先遍歷，最後在做儲存結果時改變儲存的順序並隨著列數的不同將值依序放入結果陣列的後頭或是前頭即可。

分享到