构造二叉树

构造二叉树

• 通过先序序列和中序序列

 private treeNode buildTree(int[] preorder, int[] inorder){
        if(preorder.length==0 || inorder.length==0) {
            return null;
        }
        treeNode root = new treeNode(preorder[0]);
        for(int i=0;i<preorder.length;++i) {
            if(preorder[0]==inorder[i]) {
                int[] preLeft = Arrays.copyOfRange(preorder,1,i+1);
                int[] preRight = Arrays.copyOfRange(preorder,i+1,preorder.length);
                int[] inLeft = Arrays.copyOfRange(inorder,0,i);
                int[] inRight = Arrays.copyOfRange(inorder,i+1,inorder.length);
                root.left = buildTree(preLeft,inLeft);
                root.right = buildTree(preRight,inRight);
                break;
            }
        }
        return root;
    }
    public void build(int[] preorder, int[] inorder){
        root=buildTree(preorder,inorder);
    }

• 通过先序和后序序列

   private treeNode constructFromPrePost(int[] pre, int[] post) {
          if (pre.length == 0) return null;
          treeNode root = new treeNode(pre[0]);
          if (pre.length == 1) return root;
          int distance = 0;
          for (int i = 0; i < pre.length; ++i) {
              if (post[i] == pre[1])
                  distance = i + 1;
          }
          root.left = constructFromPrePost(Arrays.copyOfRange(pre, 1, distance+1), Arrays.copyOfRange(post, 0, distance));
          root.right = constructFromPrePost(Arrays.copyOfRange(pre, distance+1,pre.length), Arrays.copyOfRange(post, distance, pre.length-1));
          return root;
      }
      public void build(int[] preorder, int[] posOrder){
          root=constructFromPrePost(preorder,posOrder);
      }

• 通过中序和后序序列

     private treeNode buildBinaryTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
          if (inStart > inEnd)
              return null;
          int rootVal = postorder[postEnd];
          int index = map.get(rootVal);
          int size = index - inStart;//左子树的节点数量
          treeNode root = new treeNode(rootVal);
          root.left = buildBinaryTree(inorder, inStart, index - 1, postorder, postStart, postStart + size - 1);
          root.right = buildBinaryTree(inorder, index + 1, inEnd, postorder, postStart + size, postEnd - 1);
          return root;
      }
      public void build(int[] inorder, int[] postorder){
          for(int i=0;i<inorder.length;i++){
              map.put(inorder[i], i);//放到类中作为全局变量
          }
          root=buildBinaryTree(inorder,0,inorder.length-1,postorder,0, postorder.length-1);
      }
  }