二叉树的遍历方法

发表于 标签 ，

二叉树的遍历方法有三种，分别是前序遍历，中序遍历和后序遍历。其中的前、中、后分别表示根节点在遍历中被访问的次序。因此，各个遍历方式的访问顺序如下所示：

前序遍历：根节点 --> 左子树 --> 右子树 中序遍历：左子树 --> 根节点 --> 右子树 后序遍历：左子树 --> 右子树 --> 根节点

下面通过 python 分别实现这三种遍历的递归方法和非递归方法，首先定义每个节点如下所示

1
2
3
4
5
6
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

前序遍历

递归实现

递归实现的方法非常简单，就是先访问根节点，然后访问左子树，最后访问右子树即可。实现代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
def preorderTraversal(root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    result = []
    if root == None:
        return result
    result.append(root.val)
    result += preorderTraversal(root.left)
    result += preorderTraversal(root.right)
    return result

非递归实现

非递归的方法通过栈来实现，流程如下 （1）将根节点设为当前节点 （2）记录当前节点 C 的值，然后将 C 入栈，将当前节点设为 C 的左子节点 （3）重复步骤（2）直到访问到空叶子节点，然后从栈中弹出一个元素 D，并将当前节点设为 D 的右子节点，重复步骤（2） （4) 重复步骤（2）~（3）直到栈为空

实现代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def preorderTraversal(root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    stack, result = [], []
    curr_node = root
    while len(stack) != 0 or curr_node!= None:
        if curr_node != None:
            result.append(curr_node.val)
            stack.append(curr_node)
            curr_node = curr_node.left
        else:
            tmp = stack.pop()
            curr_node = tmp.right
    return result

中序遍历

递归实现

递归实现也非常简单，按照顺序访问即可，实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
def inorderTraversal(root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    result = []
    if root == None:
        return result
    result += inorderTraversal(root.left)
    result.append(root.val)
    result += inorderTraversal(root.right)
    return result
### 非递归实现

非递归实现的过程类似于前序遍历的非递归实现，只是在记录节点的时间不同，中序周游记录是在元素从栈里弹出的时候才记录元素的值。实现的步骤如下：

（1）将根节点设为当前节点 （2）将当前节点 C 入栈，然后将当前节点设为 C 的左子节点 （3）重复步骤（2）直到访问到空叶子节点，然后从栈中弹出一个元素 D，记录元素 D 的值，并将当前节点设为 D 的右子节点，重复步骤（2） （4) 重复步骤（2）~（3）直到栈为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def inorderTraversal( root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    stack, result= [], []
    curr_node = root
    while len(stack) != 0 or curr_node != None:
        if curr_node != None:
            stack.append(curr_node)
            curr_node = curr_node.left
        else:
            tmp = stack.pop()
            result.append(tmp.val)
            curr_node = tmp.right
    return result

后序遍历

递归实现

后序遍历的实现也非常简单，只需要按照顺序访问即可，实现代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
def postorderTraversal(root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    result = []
    if root == None:
        return result
    result += postorderTraversal(root.left)
    result += postorderTraversal(root.right)
    result.append(root.val)
    return result

非递归实现

后续遍历的非递归实现利用了一点小技巧，就是先进行根节点-->右子树-->左子树的遍历，然后将得到的结果进行反转（reverse）即可。这是因为当根节点最后访问时无法确定何时该记录这个值。

实现的过程也类似于前序遍历，具体过程如下： （1）将根节点设为当前节点 （2）记录当前节点 C 的值，然后将 C 入栈，将当前节点设为 C 的右子节点 （3）重复步骤（2）直到访问到空叶子节点，然后从栈中弹出一个元素 D，并将当前节点设为 D 的左子节点，重复步骤（2） （4) 重复步骤（2）~（3）直到栈为空

实现代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def postorderTraversal(self, root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    stack, result = [], []
    curr_node = root
    while len(stack)!=0 or curr_node != None:
        if curr_node != None:
            result.append(curr_node.val)
            stack.append(curr_node)
            curr_node = curr_node.right
        else:
            tmp = stack.pop()
            curr_node = tmp.left
    result.reverse() 
    return result