刷题系列-中序和后序遍历队列,构造对应二叉树;

假期继续刷题,也没有别的什么事情可以干。

10年积累的成都网站制作、成都网站建设经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先网站策划后付款的网站建设流程,更有嘉黎免费网站建设让你可以放心的选择与我们合作。

这个题是给出中序和后序遍历队列,构造对应二叉树;题目很简单,如下图,给出两个遍历队列,构成二叉树,这里假定没有重复点。

  刷题系列 - 中序和后序遍历队列,构造对应二叉树;

想了好几天,真是惭愧,因为一直想一次遍历就完成构造,最后发现不行;然后就硬搞出一个多重循环的遍历方法,虽然可行,但是提交后提示耗时超过限制。最后还是用递归实现的。

其实原理很简单,对于后续遍历队列,最后一个值就是整个二叉树的根节点;而这个根节点去掉后,可以把二叉树分成左右两个树,在中序队列中,按照这个根节点来拆分出可以得到左右队列,分布对应左边树和右边树的所有点。而且其实后序队列也是按照左右树节点划分的,只要知道左右树的节点数量,来划分就可以了,这个可以从中序队列划分结果获得。反复同理,再划分出来左右树继续划分,可以得到叶子节点,或者空序列;这样就完成树的构成。

代码如下:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if inorder == []:
            return None
        else:
            if len(inorder) == 1:
                return TreeNode(inorder[0])
            else:
                RootVal = postorder[-1]
                currentNode = TreeNode(RootVal)
                inorderLeft = inorder[:inorder.index(RootVal)]
                inorderRight = inorder[inorder.index(RootVal)+1:]
                postorder.pop()
                postorderLeft = postorder[:len(inorderLeft)]
                postorderRight = postorder[-len(inorderRight):] 
                currentNode.left = self.buildTree(inorderLeft,postorderLeft)
                currentNode.right = self.buildTree(inorderRight,postorderRight)
                return currentNode

  


新闻名称:刷题系列-中序和后序遍历队列,构造对应二叉树;
本文URL:http://scyanting.com/article/jpcoho.html