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

---

一、题目

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由 不同 的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

---

二、解法

简单的做法，和【前序+中序 构造二叉树】一样，对数组进行分割就好了
比如刚开始

中序序列：9 3 15 20 7
后序序列：9 15 7 20 3

后序序列的最后一个数3就是当前的根节点：
然后再对中序序列进行分割得到9 3 15 20 7，分别代表左子树 根 右子树
依据中序分割结果，对后序序列进行分割得到9 15 7 20 3，分别代表左子树 右子树 根
递归下去就好了

---

完整代码

# 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]) -> Optional[TreeNode]:
        if not inorder:
            return None
        root = TreeNode(postorder[-1])
        idx = inorder.index(postorder[-1])
        root.left = self.buildTree(inorder[ : idx], postorder[ : idx])
        root.right = self.buildTree(inorder[idx + 1 : ], postorder[idx : len(postorder) - 1])
        return root

---

原文地址：https://blog.csdn.net/qq_26521261/article/details/140593898

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！