Construct Binary Tree from Preorder and Inorder Tr

tuomao 发布于2019-08-16 10:26 / 1200人阅读

摘要：解题思路利用递归思想，先序遍历的第一个元素就是根节点，然后在中序遍历中寻找该节点，该节点左边的就是左子树，右边的是右子树。

Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

1.解题思路
利用递归思想，先序遍历的第一个元素就是根节点，然后在中序遍历中寻找该节点，该节点左边的就是左子树，右边的是右子树。

2.代码

public class Solution {
    int curroot=0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
       return  build(0,inorder.length-1,preorder,inorder);
    }
    private TreeNode build(int instart,int inend,int[] preorder, int[] inorder){
        if(curroot==preorder.length||instart>inend) return null;
        TreeNode root=new TreeNode(preorder[curroot]);
        //find mid in inorder;
        int mid=0;
        for(int i=instart;i<=inend;i++){
            if(inorder[i]==preorder[curroot]){
                mid=i;
                break;
            }
                
        }
        curroot++;
        root.left=build(instart,mid-1,preorder,inorder);
        root.right=build(mid+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.

解题思路
后序遍历，所以逻辑和上一题一样，但是我们要从后序遍历的最后一个节点开始，这样我们就得先处理右子树，再处理左子树。

2.代码

public class Solution {
    int curroot=0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        curroot=postorder.length-1;
        return  build(0,inorder.length-1,inorder,postorder);
    }
    private TreeNode build(int instart,int inend,int[] inorder, int[] postorder){
        if(curroot<0||instart>inend) return null;
        TreeNode root=new TreeNode(postorder[curroot]);
        int mid=0;
        for(int i=instart;i<=inend;i++){
            if(inorder[i]==postorder[curroot]){
                mid=i;
                break;
            }
                
        }
        curroot--;
        root.right=build(mid+1,inend,inorder,postorder);
        root.left=build(instart,mid-1,inorder,postorder);
        
        return root;
    }
}

云服务器 GPU云服务器 binary-tree binary-search-tree Inorder Preorder

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

转载请注明本文地址：https://www.ucloud.cn/yun/69807.html

[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 Traversal

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

wenshi11019 2019-08-14 17:11 评论0 收藏0
[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
leetcode449. Serialize and Deserialize BST

摘要：题目要求将二叉搜索树序列化和反序列化，序列化是指将树用字符串的形式表示，反序列化是指将字符串形式的树还原成原来的样子。假如二叉搜索树的节点较多，该算法将会占用大量的额外空间。题目要求 Serialization is the process of converting a data structure or object into a sequence of bits so that...

Honwhy 2019-08-16 16:58 评论0 收藏0
[LeetCode-Tree]Binary Tree Inorder & Preorder

摘要：代码解题思路先序遍历，同样用迭代实现，借助栈。先将根节点入栈先序遍历，所以直接出根节点因为顺序是根，左节点，右节点，所以我们在压栈的时候要先压右节点，再压左节点。所以我们自定义了一个类，添加了的属性，来表明该节点是否已经被访问过了。 Binary Tree Inorder TraversalGiven a binary tree, return the inorder traversa...

taowen 2019-08-16 10:26 评论0 收藏0