Traversal of Binary Tree

Posted on Edited on In Views: Disqus:

本文讨论了二叉树的各种遍历。

This blog discusses about all kinds of traversals in the binary tree.

如何遍历一棵树

通常来说，树的遍历有2种方式

  • Breadth First Search (BFS) 宽度优先搜索

    树的层次遍历，先遍历完一层然后再遍历下一层。

  • Depth First Search (DFS) 深度优先搜索

    树的先序遍历、中序遍历和后序遍历都是 DFS，具体的实现方式可以有两种

    • Recursion: 隐式地调用了栈
    • Iterative: 用栈或者队列来实现

photo

Tree Transverse

定义二叉树节点类

1
2
3
4
5
# Definition of TreeNode
class TreeNode:
    def __init__(self, _val):
        self.val = _val
        self.left, self.right = None, None

Binary Tree Preorder Traversal

Recursion Approach

1
2
3
4
5
6
7
def preorderTraversal(root: TreeNode):
    if root == None:
        return None
    else:
        print(root.val)
        preorderTraversal(root.left)
        preorderTraversal(root.right)

Iterative Approach

1

Binary Tree Inorder Traversal

Recursion Approach

1
2
3
4
5
6
7
def inorderTraversal(root: TreeNode):
    if root == None:
        return None
    else:
        preorderTraversal(root.left)
        print(root.val)
        preorderTraversal(root.right)

Iterative Approach

1

Binary Tree Postorder Traversal

Recursion Approach

1
2
3
4
5
6
7
def postorderTraversal(root: TreeNode):
    if root == None:
        return None
    else:
        preorderTraversal(root.left)
        preorderTraversal(root.right)
        print(root.val)

Iterative Approach

1

Binary Tree Level Order Traversal

Iterative Approach

1

Resources