문제

BST 를 inorder, preorder, postorder 방법으로 열거해서 array에다가 순서대로 담아서 return 해라.

tree  =  9              
       /   \
     6      14  
    / \       \
  2    6      21
 /          
1            

output = true

input: tree, array = []
ouput:
inorder = [1, 2, 6, 6, 9, 14, 21]
preorder = [9, 6, 2, 1, 6, 14, 21]
postorder = [1, 2, 6, 6, 21, 14, 9]

풀이

성질을 잘 기억한다.

FACT: BST 를 inorder 로 나열하게되면 sorted array 가 된다.

def inOrderTraverse(tree, array):
    if tree is None:
		return
	inOrderTraverse(tree.left, array)
	array.append(tree.value)
	inOrderTraverse(tree.right, array)
	return array
	

def preOrderTraverse(tree, array):
	if tree is None:
		return
	array.append(tree.value)
	preOrderTraverse(tree.left, array)	
	preOrderTraverse(tree.right, array)
	return array
    

def postOrderTraverse(tree, array):
	if tree is None:
		return
	postOrderTraverse(tree.left, array)	
	postOrderTraverse(tree.right, array)
	array.append(tree.value)
	return array