1、二叉树遍历的递归算法

递归实现二叉树的遍历非常直观，回顾一下递归的代码：

• 前序遍历

def preOrder(Tree node):
    if node == None:
        return
    visit(node.data)
    preOrder(node.leftchild)
    preOrder(node.rightchild)

• 中序遍历

def inOrder(Tree node):
    if node == None:
        return 
    preOrder(node.leftchild)
    visit(node.data)
    preOrder(node.rightchild)

• 后序遍历

def postOrder(Tree node):
    if node == None:
        return 
    preOrder(node.leftchild)
    preOrder(node.rightchild)
    visit(node.data)

他们的直观区别仅仅在于visit(node.data)的位置或者说顺序发生了改变

2、二叉树遍历非递归算法转化的来龙去脉

为什么要转化为非递归算法

递归会消耗较多的栈空间，并且不断的函数调用和返回会消耗更多的时间

借助栈非递归化

递归，本质上是函数帧不断出入栈的过程。那么，我们可以直接利用栈的数据结构来模拟递归的过程，转化成非递归的代码实现

非递归化的结点入出栈过程

入栈+出栈+访问

• 什么时候结点入栈
• 什么时候结点出栈
• 什么时候访问结点

要解决上面3个问题，可以对应递归形式的代码：

• 递归调用导致当前函数环境入栈；
• 递归返回导致栈顶的函数环境出栈；
• visit行是对当前结点进行访问，并不涉及任何出入栈操作。其中，访问结点可以是打印，也可以是将结点的值加入某个列表，等等

因为对结点的访问和出入栈没有关系，因此我们先忽略递归代码中的visit语句。此时观察三种遍历的递归代码，可以发现它们的结点出入栈顺序一模一样，重复一次，出入栈顺序一模一样

这里的代码分析很重要！！！

def xxxOrder(Tree node):
    if node == None:
        return 
    
    # A.因为下面要进入递归调用的xxxOrder(node.leftchild)，后面还得回到node的
    # 因此只要一执行xxxOrder(node.leftchild)，node就会入栈
    xxxOrder(node.leftchild)
    # B.当xxxOrder(node.leftchild)执行完毕返回，即左子树探索完了
    # 控制权自然回到结点node所在的这个函数体，那么结点node就不需要存了。所以，当xxxOrder(node.leftchild)执行完毕返回，node出栈
    
    # C.因为下面要进入递归调用的xxxOrder(node.rightchild)，后面也还得回到node的
    # 因此只要一执行xxxOrder(node.rightchild)，node就又会再次入栈
    xxxOrder(node.rightchild)
    # D.当xxxOrder(node.rightchild)执行完毕返回，即右子树探索完毕，node出栈

可以清晰地看到，递归时，结点node要走完自己的函数体，经历了2次入栈出栈过程

那么，我们有必要完全模仿这样的2次入出栈的过程吗？当然没有必要
在弄清楚结点出入栈的过程之外，我们更要弄清楚结点出入栈的作用到底是什么

结点node入出栈的作用，很重要！！！

• 对于前序遍历，结点node在调用xxxOrder(node.leftchild)之前就被访问并入栈，在xxxOrder(node.leftchild)返回后出栈，此时node自己以及它的左子树全部都被访问了，它的出栈仅仅是为了获得接下来的node.rightchild。也就是说，node的第一次出栈，是为了接下来获得它的右孩子。这时，node没有再次入栈的必要
• 对于中序遍历，结点node在xxxOrder(node.leftchild)返回后出栈。node出栈是为了访问node本身+获得接下来的node.rightchild，此时node的左子树和自己本身都被访问了，在获得node.rightchild之后，接下来的一切都和node无关。这时，node也没有再次入栈的必要
• 对于后序遍历，结点node在xxxOrder(node.leftchild)返回后出栈，是为了获得接下来的node.rightchild；同时，结点node还需要再次入栈，因为它需要在xxxOrder(node.rightchild)返回后，访问自己。因此，后序遍历是比较特殊的

3、非递归形式的基础代码

基于上面分析，自然而然，非递归化的基本代码就可以写出来了！

对于前序遍历和中序遍历：

def search(TreeNode):
    
    stack = list()
    
    # A.当TreeNode不为None时, 不断入栈TreeNode
    while TreeNode != None:
        # visit(TreeNode)  # 前序
        stack.append(TreeNode)
        TreeNode = TreeNode.left
        
    # 当栈不为空时
    while stack:
        # B.栈顶元素出栈
        top = stack.pop(-1)
        # visit(top)  # 中序
        
        # C.以top.right为根结点，重复ABC
        t = top.right  # 如果是多叉树，则是 for t in top.lefted_childs:
        while t != None:
            # visit(t)  # 前序
            stack.append(t)
            t = t.left

对于后序遍历：

def search(TreeNode):
    
    stack = list()
    last_pop_node = None
    
    # 当TreeNode不为None时, 不断入栈TreeNode
    while TreeNode != None:
        stack.append(TreeNode)
        TreeNode = TreeNode.left
        
    # 当栈不为空时
    while stack:
        
        # 获取栈顶结点top，并判断是否出栈
        top = stack[-1]
        t = top.right
        # 如果top无右子树 or 上一个pop的结点是top的右孩子，说明top的右子树访问完毕，出栈top并访问
        if t is None or t == last_pop_node:
            last_pop_node = stack.pop(-1)
            visit(last_pop_node)
        
        # 否则top不出栈，top的右子树入栈
        else:
            while t != None:
                stack.append(t)
                t = t.left

例题：

给定一个二叉树，（以层次遍历顺序的list作为输入），返回它的 后序 遍历
示例:
输入: [1,null,2,3]
1
\
2
/
3

输出: [3,2,1]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        stack = list()
        last_pop_node = None
        
        # 当root不为None时, 不断入栈root
        while root != None:
            stack.append(root)
            root = root.left
            
        # 当栈不为空时
        while stack:
            
            # 获取栈顶结点top，并判断是否出栈
            top = stack[-1]
            t = top.right
            # 如果top无右子树or上一个pop的结点是top的右孩子，说明top的右子树访问完毕
            if t is None or t == last_pop_node:
                last_pop_node = stack.pop(-1)
                result.append(last_pop_node.val)
            
            # 否则top不出栈，top的右子树入栈
            else:
                while t != None:
                    stack.append(t)
                    t = t.left
        return result