二叉树的遍历：递归、非递归和分层

首先创建一棵树，用于测试

     A
   /   \
  B     C
 /    /   \
D    E     F
      \   / \
       G H   I

建树语句：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

L = {'A': TreeNode('A'),'B': TreeNode('B'),'C': TreeNode('C'),'D': TreeNode('D'), 'E': TreeNode('E'), 'F': TreeNode('F'),'G': TreeNode('G'), 'H': TreeNode('H'), 'I': TreeNode('I')}

L['F'].left, L['F'].right = L['H'], L['I']
L['E'].right = L['G']
L['C'].left, L['C'].right = L['E'], L['F']
L['A'].left, L['A'].right = L['B'], L['C']
L['B'].left = L['D']
root = L['A']

递归遍历

递归遍历用了递归，不借助于栈和队列。而循环遍历要用到栈，分层遍历要用到队列。

先根遍历

def preroot(root):
    return [] if root is None else  [root.val] + preroot(root.left) + preroot(root.right)

结果：

['A', 'B', 'D', 'C', 'E', 'G', 'F', 'H', 'I']

中根遍历

def midroot(root):
    return [] if root is None else midroot(root.left) + [root.val] + midroot(root.right)

结果：

['D', 'B', 'A', 'E', 'G', 'C', 'H', 'F', 'I']

后根遍历

def postroot(root):
    return [] if root is None else postroot(root.left) + postroot(root.right) + [root.val]

结果：

['D', 'B', 'G', 'E', 'H', 'I', 'F', 'C', 'A']

非递归遍历

非递归遍历就是循环遍历，要用到栈，而非队列；而层次遍历要用队列，而非栈。一个直观解释：

• 从递归遍历的代码可以看出遍历序列的一个性质：深度优先遍历（包括先序、中序和后序）的打印序列，节点、其左子树序列和右子树序列这三者不会有两两交叉，即节点不会在其左子树或右子树序列里被打印，其左子树和右子树序列也是分开的。而且，打印序列里的左子树序列总是位于右子树序列之前。
• 遍历树结构时，总是先拿到节点，然后才能拿到其孩子。
  • 对于中序、后序遍历里的节点和左子树，节点总是先被添加进该数据结构，等待左子树所有节点被打印之后，才会把该节点取出并打印。显然该数据结构是栈而非队列。
  • 对于先序如果该数据结构用队列，每个循环访问一个队列元素，而且左右孩子都要添加进队列，那么势必有节点的左孩子的孩子节点位列该节点的右孩子之后，而队列里位置先后意味着访问顺序的先后。
• 而层次遍历可以先进来先打印，故要用队列，而不是栈。

难点：

• 三个概念：拿到节点，访问节点，打印节点。
  • 拿到节点，是节点首次进栈，有的程序一个节点只进栈一次
  • 访问节点，是从栈里读取（不出栈）或者抛出节点
  • 打印节点，是从栈里抛出节点并打印
• 先根遍历里，拿到节点先入栈；第一次访问时，就打印节点值并将其从栈里抛出并将其两个孩子节点压入栈，因此只访问一次。
• 在中根和后根遍历里，拿到节点之后先入栈。第一次访问节点并不打印其值，而是先入栈其左孩子节点，或者全部的两个孩子节点。第二次访问是才要抛出栈并打印，如果右孩子在第一次访问时未入栈，则还要入栈其右孩子节点。由于两访问时的操作不同，需要对该访问次数有个记录才行。

先根遍历

抛出栈并打印节点值后，先入栈右孩子，再入栈左孩子。

def npreroot(root):
    res = []
    stack = []
    if root is None:
        return res
    stack.append(root)
    while len(stack) > 0:
        node = stack.pop(-1)  
        res.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return res

中根遍历

节点和状态绑定执行入栈出栈

• 第一次访问对节点做访问记录，不打印节点值而是去压其左孩子节点入栈（毕竟中序遍历，即遍历完左子树再访问该节点的值）
• 第二次访问打印该节点的值并抛出栈，以及压其右孩子节点入栈。

def nmidroot(root):
    res, stack = [], []
    if not root:
        return res
    stack.append((root, False))
    while len(stack) > 0:
        node, visited = stack.pop()
        if visited:
            res.append(node.val)
            if node.right:
                stack.append((node.right, False))
        else:
            stack.append((node, True))
            if node.left:
                stack.append((node.left, False))
    return res

贪婪策略找最深左孩子

• 访问每个节点时，先用贪婪找到其最深的左孩子，该过程中找到的所有左孩子依次入栈，然后依次出栈打印。
• 打印每个节点时，查看该节点有无右孩子，如果有则入栈。
• 贪婪策略和变量nextn共同发挥了log记录状态的作用。贪婪策略的存在，使得不用再根据节点访问状态来决定是是访问左孩子还是打印或者访问右孩子。如果nextn为空，则打印节点；不然继续将孩子压入栈。

def nmidroot(root):
    if not root: 
        return []
    
    res, stack = [], []   
    nextn = root # 下一个要入栈的节点
    while nextn or stack:         
        while nextn: 
            stack.append(nextn)
            nextn = nextn.left 
        current = stack.pop() # 要打印的节点
        res.append(current.val) 
        nextn = current.right     
    
    return res

后根遍历

状态记录和节点绑定入栈，左右孩子一起入栈

• 后根遍历和先根遍历，都可以左右孩子一起入栈，这能减少程序逻辑的工作量。原因在于，左右孩子之间没有根节点。

def npostroot(root):

    if root is None: 
        return []
        
    res, stack = [], [(root, False)]   
    while stack:
        current, visited = stack.pop()
        if visited: # 只有访问状态为True的节点才能被操作
            res.append(current.val)
        else:
            stack.append((current, True))
            if current.right:
                stack.append((current.right, False))
            if current.left:
                stack.append((current.left, False))               
    return res

右孩子在打印节点之后入栈，有右子树会被访问三次

循环（访问）次数偏多的原因：没有利用左右孩子一起入栈这个特性，反而最大限度地利用log来查询节点状态。

• 确定左子树已经访问（打印）完毕之后才将右孩子入栈
• 有右孩子的节点会被访问三次，无右孩子的节点会被访问两次
  • 有右孩子的，第二次访问不打印，而是将右孩子入栈；第三次访问时右子树已被访问并打印，才打印本节点
  • 无右孩子的，第二次就打印

def npostroot(root):
    stack = [root]
    log = []
    res = []
    while len(stack) > 0:
        node = stack[-1]
        if node not in log: # 第一次访问
            log.append(node)
            if node.left:
                stack.append(node.left)     
        else: 
            # 第二次访问，没有右孩子或者右子树已被访问的时候，打印节点值
            # 如果有右孩子且右孩子未被访问，则不打印该节点，而是将其右孩子节点入栈
            if not node.right: # 没有右节点，则打印，属于第二次访问本节点
                res.append(stack.pop(-1).val)
            else:
                if node.right not in log:  
                    # 右节点未被访问过，也意味着右子树节点都未被拿到过，属于第二次访问，还会有第三次访问
                    stack.append(node.right)
                else: # 右子树被访问过，属于第三次访问本节点
                    # 右孩子被访问过，在这里也意味着打印过，也意味着整个右子树打印过
                    res.append(stack.pop(-1).val)
    return res

贪婪策略，入栈和出栈两个迭代

• 左孩子迭代入栈：访问每个节点时，先用贪婪策略找到其最深的左孩子，该过程中找到的所有左孩子依次入栈，直到没有左孩子。
• 迭代出栈：依次出栈，打印，直到节点有右孩子。有右孩子且右子树未被访问，则对右孩子做左孩子迭代入栈操作。

def npostroot(root):
    res, stack = [], []
    nextn = root # 下一个压入栈的节点
    while nextn or len(stack) > 0:
        while nextn:
            stack.append((nextn, False))
            nextn = nextn.left
        while len(stack) > 0:
            node, visited = stack.pop(-1)
            if not visited:
                stack.append((node, True))
                nextn = node.right
                break
            else:
                res.append(node.val)
    return res

利用打印节点和栈顶节点的关系来推测状态

节点状态、访问次数，其实意味着是从左子树回来还是从右子树回来，那么如果能利用打印节点和栈顶节点的关系来推测状态，就可以不用记录节点状态或者访问次数。

def npostroot(root):
    stack = []
    nextn = root # 下一个要入栈的节点
    res = []
    
    while nextn or len(stack) > 0:
        while nextn:
            stack.append(nextn)
            nextn = nextn.left if nextn.left else nextn.right 
        node = stack.pop() # 出栈并打印的节点
        res.append(node.val)
        if len(stack) > 0 and stack[-1].left == node: 
            # 从栈顶二叉树的左子树回来，就直接将右孩子压入栈
            nextn = stack[-1].right
        else:
            # 从栈顶二叉树的右子树回来，就访问栈顶二叉树的根节点
            nextn = None
    return res

利用后序的反序列与先序关系

后序遍历的顺序是左右根，那么其反序是根右左，和先序遍历的根左右的左右顺序相反，那么只要把代码里访问左右节点的顺序互换就好了。

def npostroot(root):
    res = []
    stack = []
    if root is None:
        return res
    stack.append(root)
    while len(stack) > 0:
        node = stack.pop(-1)  
        res.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return res[::-1]

分层遍历

与先根、后根、中根遍历不同，分层遍历里同一层的节点在同一个访问批次，它们的孩子节点在之后的批次被访问。这种区别导致分层遍历可以用队列这种数据结构，而不是栈。

分层遍历属于广度优先遍历，而先根、中根和后根都是深度优先遍历。

def levelroot(root):
    queue = [root]
    res = []
    while len(queue) > 0:
        node = queue.pop(0)
        res.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return res

结果：

['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']