LeetCode <dfs>105&106 Construct Binary Tree

原创

大学里的混子

修改于 2018-11-15 14:56:25

4830

修改于 2018-11-15 14:56:25

文章被收录于专栏：LeetCodeLeetCode

105.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.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

题目大意：根据二叉树的前序和中序的遍历结果，重建二叉树

解法一：

     public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null|| inorder==null) return null;
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1,map);
    }

    public TreeNode buildTree(int[] preorder,int pi,int pj, int[] inorder,int ii,int ij,HashMap<Integer,Integer> map){
        if (pi>pj) return null;
        TreeNode head = new TreeNode(preorder[pi]);
        int index = map.get(preorder[pi]);
        head.left = buildTree(preorder,pi+1,pi+index-ii,inorder,ii,index-1,map);
        head.right = buildTree(preorder,pi+index-ii+1,pj,inorder,index+1,ij,map);
        return head;
    }

解法二：

    private int pi;
    private int ii;
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        pi = 0;
        ii = 0;
        return tra(preorder, inorder, null);
    }

    private TreeNode tra(int[] po, int[] io, TreeNode root){
        if((root != null && root.val == io[ii]) || ii > io.length - 1) return null;
        TreeNode cur = new TreeNode(po[pi++]);
        cur.left = tra(po, io, cur);
        ii++;
        cur.right = tra(po, io, root);
        return cur;
    }

106.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.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

题目大意：根据二叉树的中序和后序的遍历结果，重建二叉树

解法：

  public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder == null|| inorder==null) return null;
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return buildTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1,map);
    }

    public TreeNode buildTree( int[] inorder,int ii,int ij,int[] postorder,int pi,int pj,HashMap<Integer,Integer> map) {
        if (pi>pj) return null;
        TreeNode head = new TreeNode(postorder[pj]);
        int index = map.get(postorder[pj]);
        head.left = buildTree(inorder,ii,index-1,postorder,pi,pi+index-ii-1,map);
        head.right = buildTree(inorder,index+1,pj,postorder,pi+index-ii,pj-1,map);
        return head;
        
    }

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

其他

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

其他

登录后参与评论

0 条评论

热度