leetcode-106-根據中序和后序遍歷，構造二叉樹

widuu 發布于2019-07-30 16:04 / 2968人閱讀

摘要：題目描述以為中心進行分類題目分析根據中序和后序遍歷，構造二叉樹。根據動態規劃方法，找出循環的共性。構造子二叉樹，需要節點，和左右連接，從后序遍歷找出根節點，從對目標序列進行切分，如此往復。

題目描述：

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二叉樹遍歷非遞歸二叉樹遍歷

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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