定义树结点的结构

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

以下代码均以这棵树为例：

本文唯一指定用树

这棵树的四种遍历结果为：

  • 前序遍历：3 9 20 15 7
  • 中序遍历：9 3 15 20 7
  • 后序遍历：9 15 7 20 3
  • 层序遍历：3 9 20 15 7

二叉树的重建

没有树怎么遍历，先从建树开始。

从前序遍历和中序遍历重建二叉树

  1. 前序遍历首个元素为根节点root的值

  2. 在中序遍历中搜索根节点的索引，可将中序遍历划分为[左子树|根节点|右子树]

  3. 根据中序遍历中的左右子树的数量，可将前序遍历划分为[根节点|左子树|右子树]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def buildTree(preorder,inorder):
    node2inorder_id = {}
    for i in range(len(inorder)):
        node2inorder_id[inorder[i]] = i

    
    def recur(pre_root,in_left,in_right):
        if in_left>in_right: return
        root_val = preorder[pre_root]
        root = TreeNode(root_val)
        i = node2inorder_id[root_val]
        root.left = recur(pre_root+1,in_left,i-1)
        root.right = recur(i-in_left+pre_root+1,i+1,in_right)#左子树的长度加上根的位置再加一
        return root

    return recur(0,0,len(inorder)-1)

从层序遍历恢复二叉树

1
2
3
4
5
6
7
8
9
10
11
def reconstruct_from_levelOrder(levelorder,index):
    if levelorder[index]==-1:
        return 
    root = TreeNode(levelorder[index])
    left = 2*index+1
    right = 2*index+2
    if left<len(levelorder):
        root.left = reconstruct_from_levelOrder(levelorder,left)
    if right<len(levelorder):
        root.right = reconstruct_from_levelOrder(levelorder,right)
    return root

二叉树的遍历

现在我们通过上面的重建方式可以得到这棵树的根结点

1
2
3
4
5
6
preorder_list = [3,9,20,15,7]
inorder_list = [9,3,15,20,7]
root = buildTree(preorder_list,inorder_list)
或
levelorder_list = [3,9,20,-1,-1,15,7] #空的位置的结点值为-1
root = reconstruct_from_levelOrder(levelorder_list,0)

递归实现

1
2
3
4
5
def preOrder(root):
    if not root: return 
    print(root.val,end=' ')
    preOrder(root.left)
    preOrder(root.right)
1
2
3
4
5
def inOrder(root):
    if not root: return
    inOrder(root.left)
    print(root.val,end = ' ')
    inOrder(root.right)
1
2
3
4
5
def postOrder(root):
    if not root: return 
    postOrder(root.left)
    postOrder(root.right)
    print(root.val,end =' ')

非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
def preOrder_(root):
    result = []
    stack = []
    
    while stack or root:
        while root:
            stack.append(root)
            result.append(root.val)
            root = root.left
        root = stack.pop()
        root = root.right
    print(result)
1
2
3
4
5
6
7
8
9
10
11
12
def inOrder_(root):
    result = []
    stack = []

    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        result.append(root.val)
        root = root.right
    print(result)
1
2
3
4
5
6
7
8
9
10
11
12
def postOrder_(root):
    stack1 = []
    stack2 = []
    stack1.append(root)
    while stack1:
        node = stack1.pop()
        stack2.append(node.val)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    print(stack2[::-1])
1
2
3
4
5
6
7
8
9
10
11
12
def postOrder_2(root):
    result = []
    stack = []
    
    while stack or root:
        while root:
            stack.append(root)
            result.append(root.val)
            root = root.right
        root = stack.pop()
        root = root.left
    print(result[::-1])
1
2
3
4
5
6
7
8
9
10
11
12
13
def levelOrder_(root):
    queue = [root]
    result = []

    while queue:
        temp = []
        for _ in range(len(queue)):
            node = queue.pop(0)
            result.append(node.val)
            if node.left : temp.append(node.left)
            if node.right: temp.append(node.right)
        queue.extend(temp)
    print(result)

面鲸公众号的神奇框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def preOrder_mianjing(root):
    stack = []
    stack.append((root,False))
    result = []

    while stack: 
        root,visited = stack.pop()
        if not root:
            continue
        if visited:
            result.append(root.val)
        else:
            stack.append((root.right,False))
            stack.append((root.left,False))
            stack.append((root,True))
    print(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def inOrder_mianjing(root):
    stack = []
    stack.append((root,False))
    result = []

    while stack: 
        root,visited = stack.pop()
        if not root:
            continue
        if visited:
            result.append(root.val)
        else:
            stack.append((root.right,False))
            stack.append((root,True))
            stack.append((root.left,False))
    print(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def postOrder_mianjing(root):
    stack = []
    stack.append((root,False))
    result = []

    while stack: 
        root,visited = stack.pop()
        if not root:
            continue
        if visited:
            result.append(root.val)
        else:
            stack.append((root,True))
            stack.append((root.right,False))
            stack.append((root.left,False))
    print(result)

如有错误、无法得出正确结果，请在评论区指出，感谢！