LeetCode <dfs>105&106 Construct Binary Tree

大学里的混子

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;
        
    }

LeetCode算法解题2

LeetCode <dfs>105&106 Construct Binary Tree

105.Construct Binary Tree from Preorder and Inorder Traversal

解法一：

解法二：

106.Construct Binary Tree from Inorder and Postorder Traversal

解法：

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐