二叉树的重建

r囧r小猫 2024-04-18 08:14 12阅读 0赞

### 二叉树的重建 ###

*   *  题目
     *  思路
     *  二叉树的前序和中序遍历介绍：
     *  代码-Python

## 题目 ##

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

## 思路 ##

用前序遍历找到根结点，用根结点在中序遍历中切开左右子树，递归重建二叉树

## 二叉树的前序和中序遍历介绍： ##

**前序遍历：**  
通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xCX0FVVE8_size_16_color_FFFFFF_t_70]从根结点出发，则第一次到达结点A，故输出A;  
继续向左访问，第一次访问结点B，故输出B；  
按照同样规则，输出D，输出H；  
当到达叶子结点H，返回到D，此时已经是第二次到达D，故不在输出D，进而向D右子树访问，D右子树不为空，则访问至I，第一次到达I，则输出I；  
I为叶子结点，则返回到D，D左右子树已经访问完毕，则返回到B，进而到B右子树，第一次到达E，故输出E；  
向E左子树，故输出J；  
按照同样的访问规则，继续输出C、F、G；

**中序遍历：**  
就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。

从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；  
到达H，H左子树为空，则返回到H，此时第二次访问H，故输出H；  
H右子树为空，则返回至D，此时第二次到达D，故输出D；  
由D返回至B，第二次到达B，故输出B；  
按照同样规则继续访问，输出J、E、A、F、C、G；

下面将使用python代码来实现二叉树的重建

## 代码-Python ##

class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    
    def reConstructBinaryTree(pre, tin):
        if not pre:
            return None
        root_val = pre[0]
        root = TreeNode(root_val)
        i=tin.index(root_val)
        root.left = reConstructBinaryTree(pre[1:1 + i], tin[:i])
        root.right = reConstructBinaryTree(pre[1 + i:], tin[i + 1:])
        
        return root
    
    def preorder(root):
        if root:
            preorder(root.left)
            print(root.val)
            preorder(root.right)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xCX0FVVE8_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/5c2a66f9cb6b438bb16ab8e0950722b6.png