LeetCode - 从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:**
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]


返回如下的二叉树：

  3
 / \
9  20
  /  \
 15   7

前提

解决此问题的关键在于要很熟悉树的各种遍历次序代表的什么，最好能够将图画出来。本题解带你先进行中序遍历和后续遍历二叉树，然后再根据遍历结果将二叉树进行还原。


首先，来一棵树





然后再看树的遍历结果

根据中序和后序遍历结果还原二叉树

中序遍历和后续遍历的特性**


首先来看题目给出的两个已知条件中序遍历序列和后序遍历序列 根据这两种遍历的特性我们可以得出两个结论

• 在后序遍历序列中,最后一个元素为树的根节点
• 在中序遍历序列中,根节点的左边为左子树，根节点的右边为右子树

如下图所示

树的还原过程描述

根据中序遍历和后续遍历的特性我们进行树的还原过程分析

• 首先在后序遍历序列中找到根节点(最后一个元素)
• 根据根节点在中序遍历序列中找到根节点的位置
• 根据根节点的位置将中序遍历序列分为左子树和右子树
• 根据根节点的位置确定左子树和右子树在中序数组和后序数组中的左右边界位置
• 递归构造左子树和右子树
• 返回根节点结束

树的还原过程变量定义

需要定义几个变量帮助我们进行树的还原


HashMap memo 需要一个哈希表来保存中序遍历序列中,元素和索引的位置关系.因为从后序序列中拿到根节点后，要在中序序列中查找对应的位置,从而将数组分为左子树和右子树

• int ri 根节点在中序遍历数组中的索引位置
• 中序遍历数组的两个位置标记 [is, ie],is是起始位置，ie是结束位置
• 后序遍历数组的两个位置标记 [ps, pe] ps是起始位置，pe是结束位置

位置关系的计算

在找到根节点位置以后，我们要确定下一轮中，左子树和右子树在中序数组和后续数组中的左右边界的位置。

• 左子树-中序数组 is = is, ie = ri - 1
• 左子树-后序数组 ps = ps, pe = ps + ri - is - 1 (pe计算过程解释，后续数组的起始位置加上左子树长度-1 就是后后序数组结束位置了，左子树的长度 = 根节点索引-左子树)
• 右子树-中序数组 is = ri + 1, ie = ie
• 右子树-后序数组 ps = ps + ri - is, pe - 1

听不明白没关系，看图就对了,计算图示如下



树的还原过程

代码

class Solution:
    def __init__(self):
        self.memo={}
        self.post=[]
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        self.memo={val:idx for idx,val in enumerate(inorder)}
        self.post=postorder
        root=self.helper(0,len(inorder)-1,0,len(self.post)-1)
        return root
    def helper(self,istart,iend,pstart,pend):
        if istart>iend or pstart>pend:
            return None
        root=self.post[pend] # 获取根结点的val
        ri=self.memo[root] # 获取根结点的索引
        node=TreeNode(self.post[pend])
        node.left=self.helper(istart,ri-1,pstart,pstart+ri-istart-1)
        node.right=self.helper(ri+1,iend,pstart+ri-istart,pend-1)
        return node

最后总结

首先新建一个hashmap，将inorder也就是中序遍历数组的值作为key，下标作为value放进去；然后用一个不同参数的buildTree函数帮助实现，其中有四个参数要注意：inL、inR、poL、poR，其中的含义顾名思义，分别代表着当前子树在后序遍历和中序遍历中的范围，从L到R的值都处于当前子树中；


代码的难点可能在于node.left和node.right这两部分，做题时可以通过画图来确定四个参数的值，其中难点可能就是左子树右端点poL+(head-inL)-1和右子树左端点poL+(head-inL)这两个边界的确定，其实只要明白中序遍历头结点左边的即为左子树，head-inL长度即为左子树长度，然后在后序遍历的左端点加上这么一段，即为右子树的左端点，同理可得左子树的右端点