完全二叉树的复原

完全二叉树是一种特殊的二叉树，其中除了最后一层之外，其他层的节点都是满的，且最后一层的节点都集中在左侧。要复原一个完全二叉树，通常需要其前序遍历或中序遍历以及后序遍历的结果。但由于完全二叉树的特殊性质，通常只需要前序遍历和中序遍历的结果就可以唯一确定一棵完全二叉树。

下面是一个基于前序遍历和中序遍历复原完全二叉树的简单算法：

  • 前序遍历结果：首先访问根节点，然后遍历左子树，最后遍历右子树。
  • 中序遍历结果：首先遍历左子树，然后访问根节点，最后遍历右子树。

算法步骤：

  1. 从前序遍历的结果中，可以确定第一个节点是根节点。
  2. 在中序遍历的结果中，找到根节点的位置。它将中序遍历结果分为两部分：左子树和右子树。
  3. 使用根节点和中序遍历中根节点的位置，将前序遍历结果分为两部分：左子树的前序遍历和右子树的前序遍历。
  4. 递归地执行上述步骤，为左子树和右子树建立完全二叉树。

下面是一个Python示例代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class TreeNode:  
    def __init__(self, val=0, left=None, right=None):  
        self.val = val  
        self.left = left  
        self.right = right  
  
def buildTree(preorder, inorder):  
    if not preorder or not inorder:  
        return None  
  
    # 前序遍历的第一个节点是根节点  
    root_val = preorder[0]  
    root = TreeNode(root_val)  
  
    # 在中序遍历中找到根节点的位置  
    root_index = inorder.index(root_val)  
  
    # 切割左子树和右子树的前序遍历和中序遍历结果  
    left_inorder = inorder[:root_index]  
    right_inorder = inorder[root_index+1:]  
    left_preorder = preorder[1:root_index+1]  
    right_preorder = preorder[root_index+1:]  
  
    # 递归地构建左子树和右子树  
    root.left = buildTree(left_preorder, left_inorder)  
    root.right = buildTree(right_preorder, right_inorder)  
  
    return root

假设有棵完全二叉树的结构如下:

1
2
3
4
5

    1  
   / \  
  2   3  
 / \ / \  
4  5 6

前序遍历（preorder）: [1, 2, 4, 5, 3, 6] 中序遍历（inorder）: [4, 2, 5, 1, 6, 3]

复原这棵完全二叉树:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# 定义前序遍历和中序遍历结果  
preorder = [1, 2, 4, 5, 3, 6]  
inorder = [4, 2, 5, 1, 6, 3]  
  
# 调用buildTree函数来复原完全二叉树  
root = buildTree(preorder, inorder)  
  
# 打印复原后的完全二叉树（这里只是简单地打印节点值，实际上可能需要递归地打印整棵树）  
def print_tree(node):  
    if not node:  
        return  
    print(node.val)  
    print_tree(node.left)  
    print_tree(node.right)  
  
print_tree(root)

运行上面的代码时，它将输出复原后的完全二叉树的节点值，按照层次遍历的顺序（左到右，上到下）：

1
2
3
4
5
6

1  
2  
4  
5  
3  
6

创建一个二叉树，并遍历二叉树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 前序遍历
def preorderTraversal(root):  
    if root is None:  
        return
    print(root.value)
    preorderTraversal(root.left)
    preorderTraversal(root.right)

# 中序遍历
def inorderTraversal(root):
    if root is None:  
        return
    inorderTraversal(root.left)
    print(root.value)
    inorderTraversal(root.right)

# 后序遍历
def postorderTraversal(root):
    if root is None:  
        return
    postorderTraversal(root.left)
    postorderTraversal(root.right)
    print(root.value)

# 创建二叉树
left = TreeNode(2,TreeNode(4),TreeNode(5))
right = TreeNode(3,TreeNode(6),TreeNode(7))
root = TreeNode(1, left, right)

preorderTraversal(root)
print("\n")
inorderTraversal(root)
print("\n")
postorderTraversal(root)

参考