成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Construct Binary Tree from Traversal 根據(jù)

caoym / 510人閱讀

摘要：二分法復(fù)雜度時(shí)間空間思路我們先考察先序遍歷序列和中序遍歷序列的特點(diǎn)。對(duì)于中序遍歷序列，根在中間部分，從根的地方分割，前半部分是根的左子樹，后半部分是根的右子樹。

Construct Binary Tree from Preorder and Inorder Traversal 
Given preorder and inorder traversal of a tree, construct the binary tree.
二分法 復(fù)雜度

時(shí)間 O(N^2) 空間 O(N)

思路

我們先考察先序遍歷序列和中序遍歷序列的特點(diǎn)。對(duì)于先序遍歷序列，根在最前面，后面部分存在一個(gè)分割點(diǎn)，前半部分是根的左子樹，后半部分是根的右子樹。對(duì)于中序遍歷序列，根在中間部分，從根的地方分割，前半部分是根的左子樹，后半部分是根的右子樹。當(dāng)我們從上向下構(gòu)建樹時(shí)，我們可以通過先序遍歷序列知道根節(jié)點(diǎn)的值，但是如何知道兩個(gè)序列是在哪里分割的呢？這就要依靠中序序列了。我們?cè)谥行蛐蛄兄姓业竭@個(gè)根的值，根據(jù)這個(gè)根的坐標(biāo)，我們可以知道這個(gè)根左子樹有多少個(gè)節(jié)點(diǎn)，右子樹有多少個(gè)節(jié)點(diǎn)。然后我們根據(jù)這個(gè)將先序遍歷序列分割，通過遞歸再次取每個(gè)部分的第一個(gè)作為根，同時(shí)為了下一次能準(zhǔn)確的計(jì)算出左右子樹各有多少節(jié)點(diǎn)，我們也要同時(shí)對(duì)中序遍歷序列進(jìn)行分割。

代碼 
public class Solution {
    
    int preStart = 0;
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0) return null;
        return helper(0,inorder.length - 1,preorder,inorder);
    }
    
    private TreeNode helper(int inStart, int inEnd, int[] preorder, int[] inorder){
        // Base情況
        if(preStart > preorder.length || inStart > inEnd){
            return null;
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        int inMid = 0;
        // 找到根在中序序列中的位置，從而知道先序中的分割點(diǎn)
        for(int i = inStart ; i <= inEnd; i++){
            if(inorder[i] == preorder[preStart]){
                inMid = i;
            }
        }
        preStart++;
        // 例如先序序列 1(234)(567) 中2是左子樹的根
        root.left = helper(inStart, inMid - 1, preorder, inorder);
        // 先序序列 1(234)(567) 中5是右子樹的根
        root.right = helper(inMid + 1, inEnd, preorder, inorder);
        return root;
    }
}
Construct Binary Tree from Inorder and Postorder Traversal 
Given inorder and postorder traversal of a tree, construct the binary tree.


Note: You may assume that duplicates do not exist in the tree.
二分法 復(fù)雜度

時(shí)間 O(N^2) 空間 O(N)

思路

中序序列仍然是以根節(jié)點(diǎn)劃分為左右兩邊，而后序序列的特點(diǎn)則是根在最后，然后在跟前面的那部分中，前面部分是左子樹，后面的部分是右子樹。所以其實(shí)我們就是把上一題給反過來了。這題我們將后序序列的指針全局化，這樣我們可以先建好右子樹，再建左子樹，而指針只要順序從后向前就行了。

代碼 
public class Solution {
    
    int postEnd = 0;
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postEnd = postorder.length - 1;
        return helper(postorder, inorder, 0, inorder.length - 1);
    }
    
    private TreeNode helper(int[] postorder, int[] inorder, int inStart, int inEnd){
        if(postEnd < 0 || inStart > inEnd){
            return null;
        }
        TreeNode root = new TreeNode(postorder[postEnd--]);
        int inMid = 0;
        // 找到中序序列的根節(jié)點(diǎn)
        for(int i = inStart; i <= inEnd; i++){
            if(inorder[i] == root.val){
                inMid = i;
                break;
            }
        }
        // 建好右子樹
        root.right = helper(postorder, inorder, inMid + 1, inEnd);
        // 建好左子樹
        root.left = helper(postorder, inorder, inStart, inMid - 1);
        return root;
    }
}

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

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

相關(guān)文章

  • [LintCode/LeetCode] Construct Binary Tree from Tr

    摘要：做了幾道二分法的題目練手，發(fā)現(xiàn)這道題已經(jīng)淡忘了，記錄一下。這道題目的要點(diǎn)在于找的區(qū)間。邊界條件需要注意若或數(shù)組為空，返回空當(dāng)前進(jìn)到超出末位，或超過，返回空每次創(chuàng)建完根節(jié)點(diǎn)之后，要將加，才能進(jìn)行遞歸。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...

    馬忠志 評(píng)論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

    張漢慶 評(píng)論0 收藏0

  • Construct Binary Tree from Traversal

    摘要：思路在的順序里，先，然后再左右。所以根據(jù)可以知道的。接著再分別在和的里面重復(fù)找以及左右的過程。首先的包括和，以及對(duì)應(yīng)的起始和結(jié)束位置，對(duì)應(yīng)的起始和結(jié)束位置。返回值為，因?yàn)槊總€(gè)里要一個(gè)，同時(shí)找到它的和，左右節(jié)點(diǎn)通過返回值獲得。同時(shí)的不需要了。 From Preorder and Inorder 思路在preorder的順序里，先root，然后再左右。所以根據(jù)preorder可以知道roo...

    wenshi11019 評(píng)論0 收藏0

  • [Leetcode] Binary Tree Traversal 二叉樹遍歷

    摘要：棧迭代復(fù)雜度時(shí)間空間遞歸棧空間對(duì)于二叉樹思路用迭代法做深度優(yōu)先搜索的技巧就是使用一個(gè)顯式聲明的存儲(chǔ)遍歷到節(jié)點(diǎn)，替代遞歸中的進(jìn)程棧，實(shí)際上空間復(fù)雜度還是一樣的。對(duì)于先序遍歷，我們出棧頂節(jié)點(diǎn)，記錄它的值，然后將它的左右子節(jié)點(diǎn)入棧，以此類推。 Binary Tree Preorder Traversal Given a binary tree, return the preorder tr...

    RaoMeng 評(píng)論0 收藏0

  • LeetCode 精選TOP面試題【51 ~ 100】

    摘要：有效三角形的個(gè)數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個(gè)數(shù)字。總結(jié)本題和三數(shù)之和很像，都是三個(gè)數(shù)加和為某一個(gè)值。所以我們可以使用歸并排序來解決這個(gè)問題。注意因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為 ...

    Clect 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<