leetcode-106-根据中序和后序遍历，构造二叉树

widuu 发布于2019-07-30 16:04 / 2971人阅读

摘要：题目描述以为中心进行分类题目分析根据中序和后序遍历，构造二叉树。根据动态规划方法，找出循环的共性。构造子二叉树，需要节点，和左右连接，从后序遍历找出根节点，从对目标序列进行切分，如此往复。

题目描述：

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]

postorder = [9,15,7,20,3]
Return the following binary tree:

    3
   / 
  9  20
    /  
   15   7


inorder =   [6,8,4,9,3,15,20,7]
postorder = [6,4,8,9,15,7,20,3]
            3
           / 
          9  20
         /  /  
        8  15   7
       / 
      6  4 ps: 以 postorder为中心进行分类

题目分析：根据中序和后序遍历，构造二叉树。根据动态规划方法，找出循环的共性。
构造子二叉树，需要节点，和左右连接，从后序遍历找出根节点，从inorder对目标序列进行切分，如此往复。

# 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, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        if not postorder:
            return None
        node_center_frompost=postorder.pop()
        index_center_inorder=inorder.index(node_center_frompost)
        node=TreeNode(node_center_frompost)
        node.left=self.buildTree(inorder[:index_center_inorder],postorder[:index_center_inorder])
        node.right=self.buildTree(inorder[index_center_inorder+1:],postorder[index_center_inorder:])
        return node

GPU云服务器云服务器二叉树遍历二叉树的遍历 JS二叉树遍历非递归二叉树遍历

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/41468.html

二叉树就是这么简单

前言只有光头才能变强。文本已收录至我的GitHub仓库，欢迎Star：https://github.com/ZhongFuCheng3y/3y 一、二叉树就是这么简单本文撇开一些非常苦涩、难以理解的概念来讲讲二叉树，仅入门观看(或复习).... 首先，我们来讲讲什么是树：树是一种非线性的数据结构，相对于线性的数据结构(链表、数组)而言，树的平均运行时间更短(往往与树相关的排序时间复杂度都...

Cruise_Chan 2019-08-19 10:43 评论0 收藏0
数据结构：二叉树

摘要：链式存储结构由于二叉树的每个结点最多有两个孩子，所以为每个结点设计一个数据域和两个指针域。最终能得到二叉树的完整结构。这篇文章主要介绍树结构中的一种特殊存在——二叉树。主要内容有：二叉树的概念二叉树的基本结构二叉树的操作概念二叉树：每个结点最多有两个子结点，两个子结点是有次序的，且子结点次序不能颠倒。两个子结点一般称之为左结点及右结点。层次：在树中，节点的层次从...

Ashin 2019-05-23 17:30 评论0 收藏0
二叉树遍历问题

摘要：已知中序遍历和后序遍历中序遍历后序遍历根据中序和后序遍历确定二叉树，跟上面的方法类似，不过这次是根据后序遍历确定根节点，根据中序遍历确定左右子树。二叉树的遍历一、遍历方法三种遍历方法，很好记，什么时候访问根节点就叫什么方法。如：先序遍历，肯定就是先访问根节点；中序遍历，就是中间访问根节点；后序遍历就是最后访问根节点。 1、先序遍历：首先访问根节点，然后先序遍历左子树，最后先序遍历...

missonce 2019-08-22 16:21 评论0 收藏0
数据结构与算法:二叉树算法

摘要：因此，根据题目给出的先序遍历和中序遍历，可以画出二叉树选参考数据结构与算法描述实现二叉树算法浅谈数据结构二叉树慕课网实现二叉树算法前端树控件腾讯软件开发面试题内容衔接上一章数据结构与算法:常见排序算法内容提要什么是树　　- 为什么使用树二叉树二叉查找树红黑树Ｂ、Ｂ＋树堆伸展树树可以点击链接感受下笔者用d3.js画的tree https://codepen...

Little_XM 2019-08-22 11:09 评论0 收藏0
刷题日记Day2 | 构造二叉树

摘要：代码实现构建二叉树节点对应的值就是后序遍历数组的最后一个元素在中序遍历数组中的索引左子树的节点个数递归构造左右子树把题目的要求细化，搞清楚根节点应该做什么，然...

Hwg 2021-11-17 09:33 评论0 收藏0