未分類

Verify Preorder Serialization of a Binary Tree

Go, LeetCode, Stack

Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.

1
2
3
4
5
6
7
     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string “9,3,4,#,#,1,#,#,2,#,6,#,#”, where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character ‘#’ representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as “1,,3”.

Example 1:

1
2
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:

1
2
"1,#"
Return false

Example 3:

1
2
"9,#,#,1"
Return false
提示 解題應用
Stack LinkedList

Default:

1
2
3
func isValidSerialization(preorder string) bool {
}

解答思路:

有了前序遍歷的紀錄照理說應該也需要有中序遍歷的紀錄才能構建出一棵樹，不過這次的前序遍歷的紀錄有包含空節點，因此單前序遍歷便能構建回一棵樹，然而題目希望我們能不以重建樹的方式來確認此樹是否為合乎規定的二元樹(也就是空節點不應該存在有子節點)，一開始先遍歷前序遍歷的紀錄，每次都將取出的節點值放入stack之中，當取出的是空節點而且在stack頂端的也是空節點(表示左右子節點皆為空節點)，此時便從stack中取出兩個節點(空節點與空節點的父節點)再放入遍歷到的空節點以取代整個子樹，如下(以”9,3,4,#,#,1,#,#,2,#,6,#,#”為例):

出現兩個空節點就以一個空節點取代整個子樹(4,#,#)

1
2
3
4
5
6
7
     _9_            _9_
    /              /
   3              3
  /        →     /
 4              #
/ \     
# #

接下來因為沒有再連續出現兩個空節點就繼續遍歷前序的紀錄，並重覆上述動作連續取代了兩組子樹

1
2
3
4
5
6
7
    _9_            _9_           _9_
   /              /             /
  3              3             #
 / \      →     / \     →     
#   1          #   #
   / \     
   # #

最後若是為一棵合法的二元樹，就會只剩下一個空節點在stack之中

1
2
3
4
5
6
7
  _9_                _9_                _9_             #
 /   \              /   \              /   \
#     2            #     2            #     #
     / \     →          / \     →                 →
     #  6               #  #
       / \
       # #

程式碼解說:

一開始先定義好stack的結構，這邊是以LinkedList來實作

1
2
3
4
type StackNode struct {
	Val  string
	Next *StackNode
}

接著就來確認前序遍歷的紀錄，因為整份紀錄是字串的關係，所以要先以逗號為區隔做切割，再來便能利用迴圈一一取出每個節點值，當取出的是空節點而且在stack頂端的也是空節點(表示左右子節點皆為空節點)，此時便從stack中取出兩個節點(空節點與空節點的父節點)再放入遍歷到的空節點以取代整個子樹，如果取出時stack中不包含父節點便直接回傳false，並不斷重覆上述動作直到最後若只剩下一個空節點在stack之中，其便為一棵合法的二元樹

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func isValidSerialization(preorder string) bool {
	var tmp *StackNode
	var top *StackNode
	pre := strings.Split(preorder, ",")
	for _, v := range pre {
		for v == "#" && top != nil && top.Val == "#" {
			top = top.Next
			if top == nil {
				return false
			}
			top = top.Next
		}
		tmp = &StackNode{v, top}
		top = tmp
	}
	return top != nil && top.Next == nil && top.Val == "#"
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
type StackNode struct {
	Val  string
	Next *StackNode
}
func isValidSerialization(preorder string) bool {
	var tmp *StackNode
	var top *StackNode
	pre := strings.Split(preorder, ",")
	for _, v := range pre {
		for v == "#" && top != nil && top.Val == "#" {
			top = top.Next
			if top == nil {
				return false
			}
			top = top.Next
		}
		tmp = &StackNode{v, top}
		top = tmp
	}
	return top != nil && top.Next == nil && top.Val == "#"
}

總結:

要透過前序遍歷的紀錄(有包含空節點)，以不重建樹的方式來確認此樹是否為合乎規定的二元樹(也就是空節點不應該存在有子節點)，其做法就是先遍歷前序遍歷的紀錄，每次都將取出的節點值放入stack之中，當取出的是空節點而且在stack頂端的也是空節點(表示左右子節點皆為空節點)，此時便從stack中取出兩個節點(空節點與空節點的父節點)再放入遍歷到的空節點以取代整個子樹，並不斷重覆上述動作直到最後若只剩下一個空節點在stack之中，其便為一棵合法的二元樹。

分享到