<strike id="mmaks"></strike>

<tfoot id="mmaks"></tfoot>

<ul id="mmaks"></ul>

算法之不定期更新（四）—— 從前序與中序遍歷序列構造二叉樹（2018-06-02）

charles_paul 發布于2019-08-26 11:57 / 1958人閱讀

摘要：樹的前序，中序遍歷的結構如下圖可以看出，通過前序遍歷可以確定根節點，再通過中序遍歷和根節點的位置可以確定出左子樹和右子樹。另外左子樹的前序遍歷和中序遍歷的順序跟在其父樹中的順序一樣。因此可以確定有一種遞歸解法。

從前序與中序遍歷序列構造二叉樹

今天帶來的是Leetcode上的一個經典題：從前序與中序遍歷序列構造二叉樹
原題干：

/**

Definition for a binary tree node.
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}

*/
/**

@param {number[]} preorder
@param {number[]} inorder
@return {TreeNode}

*/
input:

前序遍歷 preorder = [3,9,20,15,7]

中序遍歷 inorder = [9,3,15,20,7]


output： 樹的根節點
條件：
樹的結構為：{ val, left, right }

下面是我解決這個題的時候的思路

解題思路

這個題目考察的是對樹結構和樹遍歷的熟悉程度。樹的前序，中序遍歷的結構如下圖：

可以看出，通過前序遍歷可以確定根節點，再通過中序遍歷和根節點的位置可以確定出左子樹和右子樹。另外左子樹的前序遍歷和中序遍歷的順序跟在其父樹中的順序一樣。

因此可以確定有一種遞歸解法。確定根和左右子樹，遞歸用左右子樹的前序和中序順序去獲取左右子樹。

代碼

var buildTree = function(preorder, inorder) {
    if (preorder.length === 0) {
        return null
    }
    let leftTreeLen = 0
    let rightTreeLen = 0
    let tag = 1
    for (let i = inorder.length - 1; i >= 0; i--) {
        if (inorder[i] !== preorder[0]) {
            if (tag) {
                rightTreeLen++
            } else {
                leftTreeLen++
            }
        } else if (inorder[i] === preorder[0]) {
            tag = false
        }
    }
    let root = new TreeNode(preorder[0]) // 根
    root.left = buildTree(preorder.slice(1, 1 + leftTreeLen), inorder.slice(0, leftTreeLen))
    root.right = buildTree(preorder.slice(1 + leftTreeLen), inorder.slice(-rightTreeLen))
    return root
};

晚上再更新一次，目測是有非遞歸的解法的。

本期算法小分享就到這里咯（leetcode正在做完探索里的中級。）如果有什么意見或者想法歡迎在評論區和我交流

云服務器 GPU云服務器二叉樹遍歷二叉樹的遍歷 JS二叉樹遍歷非遞歸二叉樹遍歷

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/107905.html

JavaScript算法之二叉搜索樹

摘要：二叉搜索樹的特性二叉搜索樹由于其獨特的數據結構，使得其無論在增刪，還是查找，時間復雜度都是，為二叉樹的高度。二叉搜索樹的查找查找很簡單，根據左子節點比該節點小，右子節點比該節點大的原則進行循環判斷即可。什么是二叉樹二叉樹就是樹的每個節點最多只能有兩個子節點什么是二叉搜索樹二叉搜索樹在二叉樹的基礎上，多了一個條件，就是二叉樹在插入值時，若插入值比當前節點小，就插入到左節點，否則插...

khlbat 2019-08-21 16:26 評論0 收藏0
LeetCode 精選TOP面試題【51 ~ 100】

摘要：有效三角形的個數雙指針最暴力的方法應該是三重循環枚舉三個數字。總結本題和三數之和很像，都是三個數加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復雜度為 ...

Clect 2021-11-15 11:38 評論0 收藏0
數據結構：二叉樹

摘要：鏈式存儲結構由于二叉樹的每個結點最多有兩個孩子，所以為每個結點設計一個數據域和兩個指針域。最終能得到二叉樹的完整結構。這篇文章主要介紹樹結構中的一種特殊存在——二叉樹。主要內容有：二叉樹的概念二叉樹的基本結構二叉樹的操作概念二叉樹：每個結點最多有兩個子結點，兩個子結點是有次序的，且子結點次序不能顛倒。兩個子結點一般稱之為左結點及右結點。層次：在樹中，節點的層次從...

Ashin 2019-05-23 17:30 評論0 收藏0
數據結構與算法:二叉樹算法

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

Little_XM 2019-08-22 11:09 評論0 收藏0