## 建树

class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None

class BinaryTree:
def __init__(self, arr):
self.root = TreeNode(arr[0])
for item in arr[1:]:
pre = self.root
cur = self.root
while cur != None:
pre = cur
if item < cur.val:
cur = cur.left
if cur == None:
pre.left = TreeNode(item)
break
else:
cur = cur.right
if cur == None:
pre.right = TreeNode(item)
break


## 递归法

def preorder_recursive(root, ret):
if root == None:
return
ret.append(root.val)
preorder_recursive(root.left, ret)
preorder_recursive(root.right, ret)

def inorder_recursive(root, ret):
if root == None:
return
inorder_recursive(root.left, ret)
ret.append(root.val)
inorder_recursive(root.right, ret)

def postorder_recursive(root, ret):
if root == None:
return
postorder_recursive(root.left, ret)
postorder_recursive(root.right, ret)
ret.append(root.val)


## 非递归-栈模拟法

### 前序遍历

from collections import deque

def preorder_iterate(root):
ret = []
stack = deque([root])
while len(stack) > 0:
top = stack.pop()
ret.append(top.val)
if top.right != None:
stack.append(top.right)
if top.left != None:
stack.append(top.left)
return ret


### 中序遍历

def inorder_iterate(root):
ret = []
stack = deque([])
cur = root
while cur != None or len(stack) > 0:
# 每次都将最左边节点进栈
while cur != None:
stack.append(cur)
cur = cur.left
# 这个时点，cur一定指空指针
top = stack.pop()
ret.append(top.val)
# 当栈顶元素存在右节点时，cur就指向它的右节点，进行新的一轮左节点入栈
if top.right != None:
cur = top.right
return ret


### 后序遍历

def postorder_iterate(root):
ret = []
stack = deque([root])
pre = None
while len(stack) > 0:
top = stack[-1]
if (top.left == None and top.right == None) or (pre != None and (pre == top.left or pre == top.right)):
ret.append(top.val)
pre = top
stack.pop()
else:
if top.right != None:
stack.append(top.right)
if top.left != None:
stack.append(top.left)
return ret


## 非递归-Morris法

morris算法刚提出的时候是用于解决中序遍历问题的，但是修改一下，也是可以应用于前序遍历和后序遍历的。

### 前序遍历

def preorder_morris(root):
ret = []
cur = root
while cur != None:
if cur.left == None:
ret.append(cur.val)
cur = cur.right
else:
p = cur.left
while p.right != None and p.right != cur:
p = p.right
if p.right == None:
ret.append(cur.val)
p.right = cur
cur = cur.left
else:
p.right = None
cur = cur.right
return ret


### 中序遍历

def inorder_morris(root):
ret = []
cur = root
while cur != None:
if cur.left == None:
ret.append(cur.val)
cur = cur.right
else:
p = cur.left
while p.right != None and p.right != cur:
p = p.right
if p.right == None:
p.right = cur
cur = cur.left
else:
p.right = None
ret.append(cur.val)
cur = cur.right
return ret


### 后序遍历

def postorder_morris(root):
pass


## 测试

import random

arr = [random.randint(0, 100) for i in range(0, 10)]
# arr = [63, 69, 30, 8, 66, 79, 38, 5, 23, 85]
print(arr)
tree = BinaryTree(arr)
ret = []
print('preorder:')
preorder_recursive(tree.root, ret)
print(ret)
ret = preorder_iterate(tree.root)
print(ret)
ret = preorder_morris(tree.root)
print(ret)

print('inorder:')
ret = []
inorder_recursive(tree.root, ret)
print(ret)
ret = inorder_iterate(tree.root)
print(ret)
ret = inorder_morris(tree.root)
print(ret)

print('postorder:')
ret = []
postorder_recursive(tree.root, ret)
print(ret)
ret = postorder_iterate(tree.root)
print(ret)

[80, 47, 97, 31, 90, 88, 54, 12, 46, 46]
preorder:
[80, 47, 31, 12, 46, 46, 54, 97, 90, 88]
[80, 47, 31, 12, 46, 46, 54, 97, 90, 88]
[80, 47, 31, 12, 46, 46, 54, 97, 90, 88]
inorder:
[12, 31, 46, 46, 47, 54, 80, 88, 90, 97]
[12, 31, 46, 46, 47, 54, 80, 88, 90, 97]
[12, 31, 46, 46, 47, 54, 80, 88, 90, 97]
postorder:
[12, 46, 46, 31, 54, 47, 88, 90, 97, 80]
[12, 46, 46, 31, 54, 47, 88, 90, 97, 80]


## 性能测试

import timeit
import random

N = 10000
arr = [random.randint(0, N) for i in range(0, N)]
tree = BinaryTree(arr)
ret = []

def test_preorder_recursive():
preorder_recursive(tree.root, ret)

def test_preorder_iterate():
ret = preorder_iterate(tree.root)

def test_preorder_morris():
ret = preorder_morris(tree.root)

def test_inorder_recursive():
inorder_recursive(tree.root, ret)

def test_inorder_iterate():
ret = inorder_iterate(tree.root)

def test_inorder_morris():
ret = inorder_morris(tree.root)

def test_postorder_recursive():
postorder_recursive(tree.root, ret)

def test_postorder_iterate():
ret = postorder_iterate(tree.root)

print('test_preorder_recursive:',
timeit.timeit(test_preorder_recursive, number=10, setup='from __main__ import test_preorder_recursive'))
print('test_preorder_iterate:',
timeit.timeit(test_preorder_iterate, number=10, setup='from __main__ import test_preorder_iterate'))
print('test_preorder_morris:',
timeit.timeit(test_preorder_morris, number=10, setup='from __main__ import test_preorder_morris'))
print('')
print('test_inorder_recursive:',
timeit.timeit(test_inorder_recursive, number=10, setup='from __main__ import test_inorder_recursive'))
print('test_inorder_iterate:',
timeit.timeit(test_inorder_iterate, number=10, setup='from __main__ import test_inorder_iterate'))
print('test_inorder_morris:',
timeit.timeit(test_inorder_morris, number=10, setup='from __main__ import test_inorder_morris'))
print('')
print('test_postorder_recursive:',
timeit.timeit(test_postorder_recursive, number=10, setup='from __main__ import test_postorder_recursive'))
print('test_postorder_iterate:',
timeit.timeit(test_postorder_iterate, number=10, setup='from __main__ import test_postorder_iterate'))

test_preorder_recursive: 0.06207431899383664
test_preorder_iterate: 0.09082036302424967
test_preorder_morris: 0.12435238715261221

test_inorder_recursive: 0.08404548815451562
test_inorder_iterate: 0.06744503695517778
test_inorder_morris: 0.11024954705499113

test_postorder_recursive: 0.08274320606142282
test_postorder_iterate: 0.1368340360932052