未分類

Binary Tree Preorder Traversal

Go, LeetCode, Stack, Tree

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的解法，解說較為詳細，基本上概念完全一樣，中序遍歷與前序遍歷的差別其實就只是對節點操作的時間不同而已。

分享到