这是一个系列，关于二叉树的，这个吧，接下来几天重点看这个了。
这个系列，把前中后都讲了吧

1.题目

给定一个二叉树，返回它的 前序/中序/后序 遍历。
要求，递归比较简单，用分治的思路解决。

2.解析

（1）递归
递归简单，定义一个函数，满足下面条件：
注意遍历起名字都站在父节点的视角
1）先序遍历：
先父再左再右
2）中序遍历：
先左再父再右
3）后序遍历：
先左再右再父
这个实现简单，就是一个先后顺序的问题，也就是list再哪append的问题。
（2）循环
循环记住一个思路即可：
树的遍历基本都要用到栈这个数据结构。
1）先序遍历
先序遍历的想法就是，每次都先更新父节点的值，因此就把append这个放在第一个循环里，这样就保证先中再左再右。
2）中序遍历
一步步来思考，先走左边，再存现在，最后走右边。一个栈，每次push左节点，直至为空，注意压进去的还是一颗树。然后这个栈每次出一个左节点，来个列表存值，然后遍历他的右节点。直到stack和root都是空。
3）后序遍历
后序遍历其实是先序遍历的逆过程。首先走左节点，然后走右节点，然后走中间节点，怎么控制右节点呢就是把左节点入栈，然后遍历完右节点，遍历左节点，最后做个倒序列。

3.python代码

#节点定义
class Node:
    def __init__(self,  x):
        self.val = x
        self.left = None
        self.right = None
#递归
#先序遍历
class Solution:
    def preorderTraversal(self, root):
        if not root:
            return []
        return [root.val] +self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
#中序遍历
class Solution:
    def preorderTraversal(self, root):
        if not root:
            return []
        return self.preorderTraversal(root.left) + [root.val] + self.preorderTraversal(root.right)
#后序遍历
class Solution:
    def preorderTraversal(self, root):
        if not root:
            return []
        return self.preorderTraversal(root.left) + self.preorderTraversal(root.right)+ [root.val] 
#循环
#先序遍历
class Solution:
    def preorderTraversal(self, root):
        stack = []
        listout = []
        cur = root
        while cur or stack:
            if cur:
                listout.append(cur.val)
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                cur = cur.right
                # if cur:
                #     listout.append(cur.val)
        return listout
#中序遍历
class Solution:
    def inorderTraversal(self, root):
        stack = []
        listout = []
        cur = root
        while stack or cur:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                listout.append(cur.val)
                cur = cur.right
        return listout
#后序遍历
    class Solution:
        def postorderTraversal(self, root):
            stack = []
            listout = []
            cur = root
            while cur or stack:
                if cur:
                    listout.append(cur.val)
                    stack.append(cur.left)
                    cur = cur.right
                else:
                    cur = stack.pop()
            return listout[::-1]