# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @return int整型一维数组
#
class Solution:
def inorderTraversal(self , root ):
res = []
self.in_order(root, res)
return res
def pre_order(self,root,res):
if not root :
return
stack = [root]
while stack:
top = stack.pop(0)
res.append(top.val)
if top.right:
stack.append(top.right)
if top.left:
stack.append(top.left)
def in_order(self,root,res):
stack = []
while root:
stack.append(root)
root = root.left
while stack:
top = stack.pop()
res.append(top.val)
right = top.right
while right:
stack.append(right)
right = right.left
return res
def post_order(self,root,res):
if not root:
return
stack = [root]
pre_node = None
while stack:
top = stack[-1]
if (not top.left and not top.right) or \
(top.right and pre_node == top.right) or \
(not top.right and pre_node==top.left):
stack.pop()
pre_node = top
res.append(top.val)
else:
if top.right:
stack.append(top.right)
if top.left:
stack.append(top.left)
return res