Construct Binary Tree from Traversal

wenshi11019 發布于2019-08-14 17:11 / 305人閱讀

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

From Preorder and Inorder

思路
在preorder的順序里，先root，然后再左右。所以根據preorder可以知道root的。而在inorder的順序里，是先左再root再右，所以在inorder里找到root之后就可以知道left和right分別有多少。接著再分別在left和right的subarray里面重復找root以及左右的過程。

dfs
首先dfs的argument包括preorder和inorder，以及preorder對應的起始和結束位置，inorder對應的起始和結束位置。返回值為TreeNode，因為每個recursion里要new一個root，同時找到它的left和right，左右節點通過返回值獲得。

cache提高速度
每次recursion里都要在inorder里找到root對應的位置，直接遍歷復雜度是O(N)，可以事先用一個全局的map來保存位置，這樣復雜度下降到O(1)。同時dfs的argument不需要inorder了。

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        /* 1. find the index of root in inorder (1st in preorder)
         * 2. all left are nodes in left subtree, right are in right subtree
         * 3. recursively
         */
         if(preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0 || preorder.length != inorder.length) return null;
         
         // cache
         map = new HashMap();
         for(int i = 0; i < inorder.length; i++) map.put(inorder[i], i);
         
         return dfs(preorder, 0, preorder.length-1, 0, inorder.length - 1);
    }
    // the corresponding index in inorder
    Map map;
    
    private TreeNode dfs(int[] pre, int ps, int pe, int is, int ie) {
        // base cases
        if(ps > pe || is > ie) return null;
        
        TreeNode root = new TreeNode(pre[ps]);
        
        int index = map.get(root.val);
        // left and right
        root.left = dfs(pre, ps + 1, ps + index - is, is, index-1);
        root.right = dfs(pre, ps + index - is + 1, pe, index+1, ie);
        return root;
    }

From Inorder and Postorder

和preorder的差不多，postorder里面root位置變一下，改成最后一個。

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap();
        for(int i = 0; i < inorder.length; i++) map.put(inorder[i], i);
        return dfs(postorder, 0, postorder.length - 1, 0, inorder.length - 1);
    }
    
    Map map;
    private TreeNode dfs(int[] post, int ps, int pe, int is, int ie) {
        // base case
        if(ps > pe || is > ie) return null;
        
        TreeNode root = new TreeNode(post[pe]);
        int index = map.get(root.val);
        root.left = dfs(post, ps, ps + index - is - 1, is, index - 1);
        root.right = dfs(post, ps + index - is, pe - 1, index + 1, ie);
        return root;
    }

云服務器 GPU云服務器 binary-tree binary-search-tree Traversal Construct

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

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

[Leetcode] Construct Binary Tree from Traversal 根據

摘要：二分法復雜度時間空間思路我們先考察先序遍歷序列和中序遍歷序列的特點。對于中序遍歷序列，根在中間部分，從根的地方分割，前半部分是根的左子樹，后半部分是根的右子樹。 Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, constru...

caoym 2019-08-14 12:32 評論0 收藏0
[LintCode/LeetCode] Construct Binary Tree from Tr

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

馬忠志 2019-08-14 15:40 評論0 收藏0
Construct Binary Tree from Preorder and Inorder Tr

摘要：解題思路利用遞歸思想，先序遍歷的第一個元素就是根節點，然后在中序遍歷中尋找該節點，該節點左邊的就是左子樹，右邊的是右子樹。 Construct Binary Tree from Preorder and Inorder TraversalGiven preorder and inorder traversal of a tree, construct the binary tree. ...

tuomao 2019-08-16 10:26 評論0 收藏0
前端 | 每天一個 LeetCode

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

張漢慶 2019-08-23 13:42 評論0 收藏0
[Leetcode] Binary Tree Traversal 二叉樹遍歷

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

RaoMeng 2019-08-14 12:25 評論0 收藏0