生活随笔
收集整理的這篇文章主要介紹了
[106].从中序与后序遍历序列构造二叉树
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
根據一棵樹的中序遍歷與后序遍歷構造二叉樹。
注意:
你可以假設樹中沒有重復的元素。
例如，給出
中序遍歷 inorder =?[9,3,15,20,7]
后序遍歷 postorder = [9,15,7,20,3]
返回如下的二叉樹：
? ? 3
? ?/ \
? 9 ?20
? ? / ?\
? ?15 ? 7
# 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:n = len(inorder)m = len(postorder)if m != n:return Nonemapper = {}for index,num in enumerate(inorder):mapper[num] = indexreturn self.build(postorder,0,n-1,mapper,0,m-1)def build(self,postorder,postLeft,postRight,mapper,inLeft,inRight):if postLeft>postRight or inLeft>inRight:return Noneroot_val = postorder[postRight]root = TreeNode(root_val,None,None)index = mapper.get(root_val)root.left = self.build(postorder,postLeft,postRight-inRight+index-1,mapper,inLeft,index-1)root.right = self.build(postorder,postRight-inRight+index,postRight-1,mapper,index+1,inRight)return root
總結
以上是生活随笔為你收集整理的[106].从中序与后序遍历序列构造二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
