未分類

Binary Tree Inorder Traversal

Go, HashTable, LeetCode, Stack, Tree

Binary Tree Inorder Traversal

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

For example:

Given binary tree [1,null,2,3],

1
2
3
4
5
1
 \
  2
 /
3

return [1,3,2].

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

解答思路:

樹的遍歷一直都是很基本綀習，一般來說都會直接用遞回的方式來實作，中序遍歷的話大致如下:

1
2
3
4
5
6
7
8
9
10
11
12
func inorderTraversal(root *TreeNode) []int {
	return travel(root, []int{})
}
func travel(node *TreeNode, inOrderList []int) []int {
	if node == nil {
		return inOrderList
	}
	inOrderList = travel(node.Left, inOrderList)
	inOrderList = append(inOrderList, node.Val)
	inOrderList = travel(node.Right, inOrderList)
	return inOrderList
}

但是這次還希望你可以嘗試不用遞回的方式來實作，這時就需要用上stack的方式來協助處理，概念上大致就是一開始不斷的遍歷左子節點並放入stack之中，待左側全數放入後才從stack取出最新的節點往右子節點移動一次，再重覆覆上述動作(遍歷左子節點)直到stack中的節點完全取出為止，而前序遍歷與中序遍歷只是差在對節點處理的時機而已，至於後序遍歷則稍為複雜點，處理節點的時機與前序遍歷相同但一開始是不斷的遍歷”右子節點”並放入stack之中，待右側全數放入後才從stack取出最新的節點往”左子節點”移動一次，也就是說後序遍歷與前序遍歷的差別是左右顛倒罷了，不過不管是遞回的方式來實作還是stack的方式來實作本質上其實是一樣的，遞回實作其實底層也是用上stack，何況兩者的時間、空間複雜度都一樣，所以說如果想要有更好的遍歷方式可以參考Morris Traversal，不用遞回也不用stack且空間複雜度只有O(1)。

程式碼解說:

如果要用上stack的方式來協助處理，一開始就要先定義stack的結構，總之就是只存樹的節點位置與下一個stack節點位置而已

1
2
3
4
type StackNode struct {
	Node *TreeNode
	Next *StackNode
}

接下來就是開始處理中序遍歷的部分，一開始先暫存根節點的位置就可以用迴圈來遍歷樹，暫存值的位置或stack最新的節點位置不為空就繼續以迴圈遍歷，如果暫存值的位置不為空就不斷的遍歷左子節點並放入stack之中，待左側全數放入後(暫存值的位置為nil)才從stack取出最新的節點(中序遍歷就是在此時對節點做處理)往右子節點移動一次，最後重覆覆上述動作直到stack中的節點完全取出為止才回傳結果陣列

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

完整程式碼:

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 inorderTraversal(root *TreeNode) []int {
	var result []int
	var top *StackNode
	tmp := root
	for tmp != nil || top != nil {
		if tmp != nil {
			top = &StackNode{tmp, top}
			tmp = tmp.Left
		} else {
			tmp = top.Node
			top = top.Next
			result = append(result, tmp.Val)
			tmp = tmp.Right
		}
	}
	return result
}

總結:

樹的遍歷一直都是很基本綀習，一般來說都會直接用遞回的方式來實作，但如果不用遞回的方式來實作，這時就需要用上stack的方式來協助處理，不過不管是遞回的方式來實作還是stack的方式來實作本質上其實是一樣的，遞回實作其實底層也是用上stack，何況兩者的時間、空間複雜度都一樣，所以說如果想要有更好的遍歷方式可以參考Morris Traversal，不用遞回也不用stack且空間複雜度只有O(1)。

分享到