Construct Binary Tree from Traversal

wenshi11019 发布于2019-08-14 17:11 / 283人阅读

摘要：思路在的顺序里，先，然后再左右。所以根据可以知道的。接着再分别在和的里面重复找以及左右的过程。首先的包括和，以及对应的起始和结束位置，对应的起始和结束位置。返回值为，因为每个里要一个，同时找到它的和，左右节点通过返回值获得。同时的不需要了。

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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