重建二叉树(分治算法)

图片文字说明


这是二叉树的标准题!务必搞懂!

思路:

  • 首先搞明白什么是前序遍历和中序遍历
  • 前序遍历性质: 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序。
  • 中序遍历性质: 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。
  • 以题目示例为例:

    • 前序遍历划分 [ 3 | 9 | 20 15 7 ]
    • 中序遍历划分 [ 9 | 3 | 15 20 7 ]

    根据以上性质,可得出以下推论:

  • 前序遍历的首元素 为 树的根节点 node 的值。

  • 在中序遍历中搜索根节点 node 的索引 ,可将 中序遍历 划分为 [ 左子树 | 根节点 | 右子树 ] 。

  • 根据中序遍历中的左 / 右子树的节点数量,可将 前序遍历 划分为 [ 根节点 | 左子树 | 右子树 ] 。

    图片文字说明

  • 通过以上三步,可确定 三个节点 :1.树的根节点、2.左子树根节点、3.右子树根节点。
    对于树的左、右子树,仍可使用以上步骤划分子树的左右子树。

  • 以上子树的递推性质是 分治算法 的体现,考虑通过递归对所有子树进行划分。

    分治算法解析:

  • 递推参数: 根节点在前序遍历的索引 root 、子树在中序遍历的左边界 left 、子树在中序遍历的右边界 right ;

  • 终止条件: 当 left > right ,代表已经越过叶节点,此时返回 nullnull ;


  • 递推工作

  • 建立根节点 node : 节点值为 preorder[root] ;

  • 划分左右子树: 查找根节点在中序遍历 inorder 中的索引 i ;
    为了提升效率,本文使用哈希表 dic 存储中序遍历的值与索引的映射,查找操作的时间复杂度为 O(1)O(1)

  • 构建左右子树: 开启左右子树递归;

    class Solution:
        def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
            def recur(pre_left: int, pre_right: int, in_left: int, in_right: int):
                if pre_left > pre_right:
                    return None
                # 前序遍历中的第一个节点就是根节点,获取索引值
                pre_root = pre_left
                # 在中序遍历中定位根节点,通过哈希映射获得inoder中的索引值
                in_root = index[preorder[pre_root]]
                # 先把根节点建立出来
                root = TreeNode(preorder[pre_root])
                # 得到左子树中的节点数目
                left_size = in_root - in_left
                # 递归地构造左子树,并连接到根节点
                # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
                root.left = recur(  pre_left + 1, 
                                    pre_left + left_size, 
                                    in_left, 
                                    in_root - 1
                                    )
                # 递归地构造右子树,并连接到根节点
                # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
                root.right = recur(pre_left + left_size + 1, 
                                    pre_right, 
                                    in_root + 1, 
                                    in_right
                                    )
                return root
            n = len(preorder)
            # 构造哈希映射,帮助我们快速定位根节点
            index = {element: i for i, element in enumerate(inorder)}
            # 开始造树
            tree = recur(0, n-1, 0, n-1)
            return tree
欢迎技术探讨