未分類

Binary Tree Preorder Traversal

Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:

Given binary tree {1,#,2,3},

1
2
3
4
5
1
\
2
/
3

return [1,2,3].

Note:

Recursive solution is trivial, could you do it iteratively?

提示 解題應用
Tree 前序遍歷
Stack LinkedList

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

解答思路:

建議可以先參考先前Binary Tree Inorder Traversal的解法,解說較為詳細,基本上概念完全一樣,中序遍歷與前序遍歷的差別其實就只是對節點操作的時間不同而已,所以本題與先前的差異就只是節點值放入結果陣列的時機,差別僅此就不再多加著墨,一樣也是不透過遞回而由stack來完成實作。

程式碼解說:

這邊只解說與先前題目程式碼的相異之處,因為中序遍歷與前序遍歷的差別其實就只是對節點操作的時間不同,所以原本中序遍歷對節點操作的時間是在從stack取頭節點出來之後,前序遍歷的時機則改為在節點放入stack之前就對節點進行操作,說操作其實就只是節點值放入結果陣列而已

1
2
3
4
5
6
7
8
9
10
11
for tmp != nil || top != nil {
if tmp != nil {
top = &StackNode{tmp, top}
result = append(result, tmp.Val)
tmp = tmp.Left
} else {
tmp = top.Node
top = top.Next
tmp = tmp.Right
}
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
type StackNode struct {
Node *TreeNode
Next *StackNode
}
func preorderTraversal(root *TreeNode) []int {
var result []int
var top *StackNode
tmp := root
for tmp != nil || top != nil {
if tmp != nil {
top = &StackNode{tmp, top}
result = append(result, tmp.Val)
tmp = tmp.Left
} else {
tmp = top.Node
top = top.Next
tmp = tmp.Right
}
}
return result
}

總結:

建議可以先參考先前Binary Tree Inorder Traversal的解法,解說較為詳細,基本上概念完全一樣,中序遍歷與前序遍歷的差別其實就只是對節點操作的時間不同而已。

分享到