题解 | #牛群的树形结构重建#
牛群的树形结构重建
https://www.nowcoder.com/practice/bcabc826e1664316b42797aff48e5153
- 题目考察的知识点 : 中序遍历和后序遍历构造二叉树
- 题目解答方法的文字分析:
- 后序遍历的最后一个元素为整棵树的根节点;
- 在中序遍历中找到根节点的位置,左边为左子树的中序遍历,右边为右子树的中序遍历;
- 根据左子树的中序遍历长度,确定后序遍历中左右子树的分界点;
- 递归地构造左右子树,返回根节点。
- 本题解析所用的编程语言: 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题的解法思路