二叉树的遍历总结

二叉树的遍历真的是又简单又复杂，以他为原型可以变出好多好多题目，但是归根结底还是要非常熟悉二叉树的遍历。递归算法就不写了，那个面试写了就是凉凉。

1. 前序遍历

 1 def preOrder(root):
 2     stack1 = []
 3     res = []
 4     cur = root
 5     while stack1 or cur:
 6         if cur:          #这一步主要是第一步放入根节点   
 7             stack1.append(cur)
 8         cur = stack1.pop() #之后每次从栈中pop数据
 9         res.append(cur.val)
10         if cur.right:
11             stack1.append(cur.right)
12         if cur.left:
13             stack1.append(cur.left)
14         cur = None
15     return res

从这里可以看出，因为是先序遍历，所以不需要保存根节点，直接push之后再pop出来。

2. 中序遍历

 1 def inOrder(root):
 2     stack1 = []
 3     res = []
 4     cur = root
 5     while stack or cur:
 6         while cur:
 7             stack1.append(cur)
 8             cur = cur.left
 9         cur = cur.pop()
10         res.append(cur.val)
11         cur = cur.right
12     return res

从这里我们可以看出，先序遍历和中序遍历整体结构是相同的，但是这里面的细小的区别才是最重要的，也就是先序是if 中序是while 原因就是在于先序的话我直接就读到根节点的值，但是中序遍历是在读完所有左子树才会读根节点，因此使用while 一直不断地把根节点压入栈中。

第二个区别是在最后cur 的复制中，先序让cur=None的原因是因为cur 已经被读取到了，我已经把cur的左子树和右子树压入栈，但是中序遍历中我们需要对根节点的右节点进行遍历，所以让cur = cur.right 就可以跳到第一行的while中。同样的，有了这个while 就不要判断if cur.right == None。

3. 后序遍历

def postOrder(root):
        stack1 = []
        res = []
        cur = root
        while stack1 or cur:
            while cur:
                stack1.append(cur)
                cur = cur.right if cur.left == None else cur.left
            cur = stack1.pop()
            res.append(cur.val)
            if stack1  and stack1[-1].left == cur: #  stack1[-1] 是cur的next 节点！
                cur = stack1[-1].right
            else:
                cur = None
        return res

后序遍历是比较复杂的，技巧也比较多。但是三种遍历的核心在于入栈，我们一定要搞清楚为什么要入栈，入栈到底要入什么。栈的顺序便是先入后出，所以不管是先序，中序，后序，只要能把握究竟要入什么，其实就掌握了二叉树的遍历的本质。后序中因为根节点是最后需要访问的，因此要最先入栈。然后入栈的是什么呢？是这个数的最左边的节点，和中序遍历不同，中序遍历只要找到第一个最左边的元素，后序遍历是要找到第一个左右子树都为空的节点。

这其实可以看出，栈中保存的是下一个需要访问的节点，而里面的while 循环，主要功能就是保存我们的路径。