题解 | #牛群的树形结构重建#

牛群的树形结构重建

https://www.nowcoder.com/practice/bcabc826e1664316b42797aff48e5153

  • 题目考察的知识点 : 中序遍历和后序遍历构造二叉树
  • 题目解答方法的文字分析:
  1. 后序遍历的最后一个元素为整棵树的根节点;
  2. 在中序遍历中找到根节点的位置,左边为左子树的中序遍历,右边为右子树的中序遍历;
  3. 根据左子树的中序遍历长度,确定后序遍历中左右子树的分界点;
  4. 递归地构造左右子树,返回根节点。
  • 本题解析所用的编程语言: Python
  • 完整且正确的编程代码
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param inOrder int整型一维数组 
# @param postOrder int整型一维数组 
# @return TreeNode类
#
class Solution:
    def buildTree(self , inOrder: List[int], postOrder: List[int]) -> TreeNode:
        if not inOrder or not postOrder:
            return None

        root_val = postOrder[-1]
        root_idx = inOrder.index(root_val)

        left_inorder = inOrder[:root_idx]
        right_inorder = inOrder[root_idx+1:]

        left_postorder = postOrder[:len(left_inorder)]
        right_postorder = postOrder[len(left_inorder):-1]

        root = TreeNode(root_val)
        root.left = self.buildTree(left_inorder, left_postorder)
        root.right = self.buildTree(right_inorder, right_postorder)

        return root
牛客高频top202题解系列 文章被收录于专栏

记录刷牛客高频202题的解法思路

全部评论

相关推荐

流浪的神仙:无恶意,算法一般好像都得9硕才能干算法太卷啦
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务