先序遍历：根左右
中序遍历：左根右
后序遍历：左右根
首先是前序遍历的代码，思想就是从最初的根节点，一直往左，这些左节点的value依次添加到result列表中，当没有左节点之后，就可以pop当前节点了，然后尝试寻找当前节点(已被pop)的右节点；
如果右节点不为空，会以该右节点为根节点继续上述操作
如果该右节点为空，那么就会pop出上一层的根节点，再来看上一层的根节点有没有右节点
def preorder(root):#递归解法
if root is None:
return []
return [root.val]+preorder(root.left)+preorder(root.right)
def preorder(root):
#非递归解法 网上用的最多的模板方法
if root is None:
return []
stack,values,node=[],[],root
while node or stack:
#这里while node or stack有两个意义
#stack是为了确保当某个节点的右节点为空时候，stack不为空(返回树的上一层)，while循环继续下去
#但是只用stack不行，因为初始化的时候stack是空的，要加一个node条件
while node:
stack.append(node)
values.append(node.val)
node=node.left
node=stack.pop()
node=node.right
return values
def preorder(root):
#我对上述代码的改写 采用do-while思想,也就是python的while True/if break
#这样代码个人认为更容易理解
if root is None:
return []
stack,values,node=[],[],root
while True:
while node:
stack.append(node)
values.append(node.val)
node=node.left
if len(stack)==0:
break
node=stack.pop()
node=node.right
return values
在前序遍历中，我们append第一个根节点之后，就一路向左，继而形成了 中-左-右 的遍历顺序。
中序遍历和前序遍历其实思想很接近，只不过中序遍历是 左-中-右
换言之，我们不append第一个根节点，而是把一路向左的那些节点先append进stack和result，当再没有左节点之后(已到最左)，就可以把pop出来的节点加入到result列表了
def inorder(root):
#一句话递归
if root is None:
return []
return self.inorderTraversal(root.left)+[root.val]+self.inorderTraversal(root.right)
def inorder(root):
if root is None:
return []
stack,values,node=[],[],root
while True:
while node:
stack.append(node)
node=node.left
if len(stack)==0:
break
node=stack.pop()
values.append(node.val)
node=node.right
return values
前序遍历和中序遍历简单是因为他们在遍历的时候都是先根，再左，然后右(只是添加val到result列表的顺序不同)。但是在后序遍历中，遍历有一定的跳跃性，左右根，如果我们能先得到这个根的信息，再根据根的信心找到它的左右，这样会变简单。
所以解法方法是找到 左-右-根 的逆序，根-右-左，用stack1来记录根-右左的节点，每次按顺序pop出 左-右-根到stack2，这样便可以得到后序遍历的列表stack2
def postorder( root):#递归方法
if root is None:
return []
return postorder(root.left)+postorder(root.right)+[root.val]
def postorder(root):
if root is None:
return []
stack1,stack2,result,node=[],[],[],root
while True:
node=stack1.pop()
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
stack2.append(node)
if len(stack1)==0:
break
while stack2:
result.append(stack2.pop().val)
return result
层次遍历就是一行一行的遍历，所以用队列queue，先进先出fifo是比较合适的，每次我们pop(0)。
def levelorder(root):
if root is None :
return []
node,result,queue=root,[],[]
queue.append(node)
while queue:
level=[]
for _ in range(len(queue)):
node=queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result