二叉树的三种遍历方式

学习二叉树时，前序中序后序遍历方式是基础知识。最近再刷Leetcode时，发现很多遍历实现的基本本方式已经忘记了，这里将各种方式的原理与代码实现整理如下；

三种遍历方式原理

三种遍历方式简单的一句话就是：根左右、左根右、左右根。

如何理解前中后序

理解前中后序的算法本身并不难，很多人直接就可以把前中后序算法结果写在纸面上。但还是要简单的说下过程：

首先看一张遍历图示：

遍历图示显示，遍历的顺序为从根节点出发，先左子树后右子树。除了根节点与空节点外每一个节点均有三个入箭头，这三个如箭头分别表示：从父节点来、从左子树返回、从右子树返回。我们可以认为在递归算法中，每个节点均被遍历了三遍，但是哪一遍访问节点，决定了前、中、后序算法。

非递归算法中，是否遍历了三遍、我无法确定。就算是使用栈实现遍历时，不同的算法策略也不尽相同。

代码实现

准备

节点定义：

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

构成树代码

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")
J = TreeNode("J")
K = TreeNode("K")
A.left = B
A.right = C
B.left = D
B.right = E
D.left = H
D.right = I
E.right = J
C.left = F
C.right = G
F.right = K

先序遍历

递归：

def frontorderTraversal(root):
    res = []
    if not root:
        return []
    def frontorder(tree):
        res.append(tree.val)
        if tree.left:
            frontorder(tree.left)
        if tree.right:
            frontorder(tree.right)
    frontorder(root)
    return res

通用框架——先序

这里的通用框架是在刷leetcode过程中，发现的一种类似于递归方式的，只需要更改部分代码，即可从先序转为中序或后序。

def frontorderTraversal( root):
    """
    1. 递归法可以一行代码完成，无需讨论；
    2. 迭代法一般需要通过一个栈保存节点顺序，我们这里直接使用列表
      - 首先，我要按照中序遍历的顺序存入栈，这边用的逆序，方便从尾部开始处理
      - 在存入栈时加入一个是否需要深化的参数
      - 在回头取值时，这个参数应该是否，即直接取值
      - 简单调整顺序，即可实现前序和后序遍历
    """
    # 迭代法
    result = []
    stack = [(1, root)]
    while stack:
        go_deeper, node = stack.pop()
        if node is None:
            continue
        if go_deeper:
            # 左右节点还需继续深化，并且入栈是先右后左
            stack.append((1, node.right))
            # 节点自身已遍历，回头可以直接取值
            
            stack.append((1, node.left))
            stack.append((0, node))
        else:
            result.append(node.val)
    return result

中序遍历

递归：

def inorderTraversal(root):
    res = []
    if not root:
        return []
    def inorder(tree):
        if tree.left:
            inorder(tree.left)
        res.append(tree.val)
        if tree.right:
            inorder(tree.right)
    inorder(root)
    return res

通用框架——中序

def inorderTraversal( root):
    result = []
    stack = [(1, root)]
    while stack:
        go_deeper, node = stack.pop()
        if node is None:
            continue
        if go_deeper:
            # 左右节点还需继续深化，并且入栈是先右后左
            stack.append((1, node.right))
            # 节点自身已遍历，回头可以直接取值
            stack.append((0, node))
            stack.append((1, node.left))
        else:
            result.append(node.val)
    return result

教材法

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        if not root:
            return []
        stack = []
        curr = root
        while  stack  or curr  :
            # 这里面写while也可以，或者写if都是可以的
            # 这里的代码有优化过
            while(curr):
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            res.append(curr.val)
            curr = curr.right     
        return res

后序遍历

递归:

def backorderTraversal(root):
    res = []
    if not root:
        return []
    def backorder(tree):
        
        if tree.left:
            backorder(tree.left)
        if tree.right:
            backorder(tree.right)
        res.append(tree.val)
    backorder(root)
    return res

通用框架——后序

def backorderTraversal( root):
    result = []
    stack = [(1, root)]
    while stack:
        go_deeper, node = stack.pop()
        if node is None:
            continue
        if go_deeper:
            stack.append((0, node))
            # 左右节点还需继续深化，并且入栈是先右后左
            stack.append((1, node.right))
            # 节点自身已遍历，回头可以直接取值
            
            stack.append((1, node.left))
            
        else:
            result.append(node.val)
    return result

QingZhi's Blog