106. 从中序与后序遍历序列构造二叉树

Difficulty
Medium
Tags
二叉树
URL
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
Star
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
返回如下的二叉树：
    3
   / \
  9  20
    /  \
   15   7

法1

思路
参考
⛹🏽‍♂️
105. 从前序与中序遍历序列构造二叉树
对中序 inorder的处理和 105题一样，因为是中序，所以找到根节点，左边自然是左子树，右边自然是右子树
对后序数组postorder的处理就不一样，因为是后序（左右中），所以找到根节点后，postorder中前len(inleft)是左子树，接着len(in_right)是右子树
 
题解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        # 基线条件
        if len(postorder) <= 2:
            if len(postorder) == 2:
                node = TreeNode(postorder[-1])
                if postorder[0] == inorder[0]: # 说明子节点在左边
                    node.left = TreeNode(inorder[0])
                else:
                    node.right = TreeNode(inorder[1])
                return node
            elif len(postorder) == 1:
                node = TreeNode(postorder[-1])
                return node
            elif len(postorder) == 0:
                return None

        cur_node = postorder[-1]
        cur_idx = inorder.index(cur_node)
        # 对中序 inorder的处理和 105题一样，
        # 因为是中序，所以找到根节点，左边自然是左子树，右边自然是右子树
        in_left = inorder[0:cur_idx]
        # 对后序数组postorder的处理就不一样，
        # 因为是后序（左右中）所以找到根节点后，postorder中前len(inleft)是左子树，接着len(in_right)是右子树
        post_left = postorder[0:len(in_left)]
        if cur_idx == len(inorder)-1: # 防止数组下标越界
            in_right = []
            post_right = []
        else:
            in_right = inorder[cur_idx+1:]
            post_right = postorder[len(in_left):-1]

        root = TreeNode(cur_node)
        root.left = self.buildTree(in_left, post_left)
        root.right = self.buildTree(in_right, post_right)
        return root
上述代码为了防止如下情况的数组下标溢出
 二叉树如下     
      7
     / 
    6 
  /  \
 3    2 

postorder = [3, 2, 6, 7]
inorder = [3, 6, 2, 7]

递归第一次时：
val = 7
idx = 3
那么 in_left = [0:3]
in_right = [4:]
可以发现此处4已经溢出了
 
但事实上，Python3中 对数组nums 取值时，下标超出 len(nums) 会报错，但是进行切片时，即使超出也不会报错，只会输出空列表，示例如下：
nums = [3, 6, 2, 7]
print(nums[0:3])
print(nums[5:])

# 输出
[3, 6, 2]
[]
所以对上述代码优化得到，且使用二叉树构造模板，简洁实现如下：
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if len(inorder) == 0:
            return None
        return self.recur(inorder, postorder)

    def recur(self, inorder, postorder):
        if len(inorder) == 0:
            return None
        if len(inorder) == 1:
            return TreeNode(inorder[-1])
        # 当前根节点的值为后顺序遍历的最后一个值
        curVal = postorder[-1]
        # 找到当前节点值在中序的位置
        curIdx = inorder.index(curVal)
        # 对于中序：curIdx 左边的为 根节点左子节点 右边的为根节点右子节点
        leftInorder = inorder[0:curIdx] 
        rightInorder = inorder[curIdx+1:]
        # 对于后序： 前len(leftInorder)个值为根节点左子节点 紧挨着的len(rightInorder)个值为右子节点
        leftPostorder = postorder[0:len(leftInorder)]
        rightPostorder = postorder[len(leftInorder):-1]

        curNode = TreeNode(curVal)
        curNode.left = self.recur(leftInorder, leftPostorder)
        curNode.right = self.recur(rightInorder, rightPostorder)

        return curNode