国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Leetcode] Construct Binary Tree from Traversal 根據

caoym / 492人閱讀

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

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

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

思路

我們先考察先序遍歷序列和中序遍歷序列的特點。對于先序遍歷序列，根在最前面，后面部分存在一個分割點，前半部分是根的左子樹，后半部分是根的右子樹。對于中序遍歷序列，根在中間部分，從根的地方分割，前半部分是根的左子樹，后半部分是根的右子樹。當我們從上向下構建樹時，我們可以通過先序遍歷序列知道根節(jié)點的值，但是如何知道兩個序列是在哪里分割的呢？這就要依靠中序序列了。我們在中序序列中找到這個根的值，根據這個根的坐標，我們可以知道這個根左子樹有多少個節(jié)點，右子樹有多少個節(jié)點。然后我們根據這個將先序遍歷序列分割，通過遞歸再次取每個部分的第一個作為根，同時為了下一次能準確的計算出左右子樹各有多少節(jié)點，我們也要同時對中序遍歷序列進行分割。

代碼 
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;
        // 找到根在中序序列中的位置，從而知道先序中的分割點
        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.
二分法 復雜度

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

思路

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

代碼 
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é)點
        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;
    }
}

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

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

相關文章

  • [LintCode/LeetCode] Construct Binary Tree from Tr

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

    馬忠志 評論0 收藏0

  • 前端 | 每天一個 LeetCode

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

    張漢慶 評論0 收藏0

  • Construct Binary Tree from Traversal

    摘要：思路在的順序里，先，然后再左右。所以根據可以知道的。接著再分別在和的里面重復找以及左右的過程。首先的包括和，以及對應的起始和結束位置，對應的起始和結束位置。返回值為，因為每個里要一個，同時找到它的和，左右節(jié)點通過返回值獲得。同時的不需要了。 From Preorder and Inorder 思路在preorder的順序里，先root，然后再左右。所以根據preorder可以知道roo...

    wenshi11019 評論0 收藏0

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

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

    RaoMeng 評論0 收藏0

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

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

    Clect 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<