leetcode-106-根據(jù)中序和后序遍歷，構(gòu)造二叉樹

widuu 發(fā)布于2019-07-30 16:04 / 2977人閱讀

摘要：題目描述以為中心進(jìn)行分類題目分析根據(jù)中序和后序遍歷，構(gòu)造二叉樹。根據(jù)動(dòng)態(tài)規(guī)劃方法，找出循環(huán)的共性。構(gòu)造子二叉樹，需要節(jié)點(diǎn)，和左右連接，從后序遍歷找出根節(jié)點(diǎn)，從對(duì)目標(biāo)序列進(jìn)行切分，如此往復(fù)。

題目描述：

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為中心進(jìn)行分類

題目分析：根據(jù)中序和后序遍歷，構(gòu)造二叉樹。根據(jù)動(dòng)態(tài)規(guī)劃方法，找出循環(huán)的共性。
構(gòu)造子二叉樹，需要節(jié)點(diǎn)，和左右連接，從后序遍歷找出根節(jié)點(diǎn)，從inorder對(duì)目標(biāo)序列進(jìn)行切分，如此往復(fù)。

# 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

云服務(wù)器 GPU云服務(wù)器二叉樹遍歷二叉樹的遍歷 JS二叉樹遍歷非遞歸二叉樹遍歷

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/41468.html

相關(guān)文章

二叉樹就是這么簡(jiǎn)單

前言只有光頭才能變強(qiáng)。文本已收錄至我的GitHub倉庫，歡迎Star：https://github.com/ZhongFuCheng3y/3y 一、二叉樹就是這么簡(jiǎn)單本文撇開一些非?？酀㈦y以理解的概念來講講二叉樹，僅入門觀看(或復(fù)習(xí)).... 首先，我們來講講什么是樹：樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，相對(duì)于線性的數(shù)據(jù)結(jié)構(gòu)(鏈表、數(shù)組)而言，樹的平均運(yùn)行時(shí)間更短(往往與樹相關(guān)的排序時(shí)間復(fù)雜度都...

Cruise_Chan 2019-08-19 10:43 評(píng)論0 收藏0
數(shù)據(jù)結(jié)構(gòu)：二叉樹

摘要：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)由于二叉樹的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，所以為每個(gè)結(jié)點(diǎn)設(shè)計(jì)一個(gè)數(shù)據(jù)域和兩個(gè)指針域。最終能得到二叉樹的完整結(jié)構(gòu)。這篇文章主要介紹樹結(jié)構(gòu)中的一種特殊存在——二叉樹。主要內(nèi)容有：二叉樹的概念二叉樹的基本結(jié)構(gòu) 二叉樹的操作概念二叉樹：每個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)，兩個(gè)子結(jié)點(diǎn)是有次序的，且子結(jié)點(diǎn)次序不能顛倒。兩個(gè)子結(jié)點(diǎn)一般稱之為左結(jié)點(diǎn)及右結(jié)點(diǎn)。層次：在樹中，節(jié)點(diǎn)的層次從...

Ashin 2019-05-23 17:30 評(píng)論0 收藏0
二叉樹遍歷問題

摘要：已知中序遍歷和后序遍歷中序遍歷后序遍歷根據(jù)中序和后序遍歷確定二叉樹，跟上面的方法類似，不過這次是根據(jù)后序遍歷確定根節(jié)點(diǎn)，根據(jù)中序遍歷確定左右子樹。二叉樹的遍歷一、遍歷方法三種遍歷方法，很好記，什么時(shí)候訪問根節(jié)點(diǎn)就叫什么方法。如：先序遍歷，肯定就是先訪問根節(jié)點(diǎn)；中序遍歷，就是中間訪問根節(jié)點(diǎn)；后序遍歷就是最后訪問根節(jié)點(diǎn)。 1、先序遍歷：首先訪問根節(jié)點(diǎn)，然后先序遍歷左子樹，最后先序遍歷...

missonce 2019-08-22 16:21 評(píng)論0 收藏0
數(shù)據(jù)結(jié)構(gòu)與算法:二叉樹算法

摘要：因此，根據(jù)題目給出的先序遍歷和中序遍歷，可以畫出二叉樹選參考數(shù)據(jù)結(jié)構(gòu)與算法描述實(shí)現(xiàn)二叉樹算法淺談數(shù)據(jù)結(jié)構(gòu)二叉樹慕課網(wǎng)實(shí)現(xiàn)二叉樹算法前端樹控件騰訊軟件開發(fā)面試題內(nèi)容銜接上一章數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法內(nèi)容提要什么是樹　　- 為什么使用樹二叉樹二叉查找樹紅黑樹Ｂ、Ｂ＋樹堆伸展樹樹可以點(diǎn)擊鏈接感受下筆者用d3.js畫的tree https://codepen...

Little_XM 2019-08-22 11:09 評(píng)論0 收藏0
刷題日記Day2 | 構(gòu)造二叉樹

摘要：代碼實(shí)現(xiàn)構(gòu)建二叉樹節(jié)點(diǎn)對(duì)應(yīng)的值就是后序遍歷數(shù)組的最后一個(gè)元素在中序遍歷數(shù)組中的索引左子樹的節(jié)點(diǎn)個(gè)數(shù)遞歸構(gòu)造左右子樹把題目的要求細(xì)化，搞清楚根節(jié)點(diǎn)應(yīng)該做什么，然...

Hwg 2021-11-17 09:33 評(píng)論0 收藏0