改进了上一个Gist中的make_tree_by_prein函数以避免过多中间字符串的产生

make-tree-by-prein.lisp

;;;; The Common Lisp version implementation of the function implemented previously in C
;;; A non-trivial implementation
(defun make-tree-by-prein (preseq inseq)
  (labels ((aux (sp ep si ei)
             (cond ((> sp ep) nil)
                   ((= sp ep) (make-tree-node (char preseq sp) nil nil))
                   (t
                    (let* ((root-value (char preseq sp))
                           (offset (position root-value inseq :start si))
                           (left (aux (1+ sp) (+ sp offset)
                                      si (+ si offset -1)))
                           (right (aux (+ sp offset 1) ep
                                       (+ si offset 1) ei)))
                      (make-tree-node root-value left right))))))
    (aux 0 (1- (length preseq)) 0 (1- (length inseq)))))

make_tree_by_prein.c

Tree make_tree_aux(char *preseq, int sp, int ep, char *inseq, int si, int ei)
{
    if (NULL == preseq || sp > ep)
        return NULL;
    if (sp == ep)
        return make_node(preseq[sp], NULL, NULL);
    else {
        char root_value = preseq[sp];
        int offset = find_position(root_value, inseq + si); /* The `offset' must not greater than the difference between `ep' and `sp'. */
        Tree left = make_tree_aux(preseq, sp + 1, sp + offset,
                                  inseq, si, si + offset - 1);
        Tree right = make_tree_aux(preseq, sp + offset + 1, ep,
                                   inseq, si + offset + 1, ei);

        return make_node(root_value, left, right);
    }
}

Tree make_tree_by_prein(char *preseq, char *inseq)
/* Second version. Avoid the duplication of many substrings. */
{
    return make_tree_aux(preseq, 0, strlen(preseq) - 1,
                         inseq, 0, strlen(inseq) - 1);
}

TreePost.java

/*
 * TreePost.java
 *
 *
 *
 * Copyright (C) 2012-10-25 liutos
 */
class TreeNode
{
    char value;
    TreeNode left, right;

    public TreeNode(char value, TreeNode left, TreeNode right)
    {
        this.value = value;
        this.left = left;
        this.right =right;
    }

    void postorderPrintTree()
    {
        postorderPrintTreeAux(this);
        System.out.println("");
    }

    void postorderPrintTreeAux(TreeNode tree)
    {
        if (tree != null) {
            postorderPrintTreeAux(tree.left);
            postorderPrintTreeAux(tree.right);
            System.out.print(tree.value);
        }
    }
}

public class TreePost
{
    String preseq, inseq;

    public static void main(String[] args)
    {
        TreePost tp = new TreePost("abfce", "bface");
        TreeNode tree = tp.makeTree();

        tree.postorderPrintTree();
    }

    public TreePost(String preseq, String inseq)
    {
        this.preseq = preseq;
        this.inseq = inseq;
    }

    public TreeNode makeTree()
    {
        return makeTreeAux(0, preseq.length() - 1, 0, inseq.length() - 1);
    }

    private TreeNode makeTreeAux(int sp, int ep, int si, int ei)
    {
        if (sp > ep) return null;
        // System.out.println("Processing " + preseq.substring(sp, ep + 1) + " and " + inseq.substring(si, ei + 1));
        if (sp == ep) {
            System.out.println("One character " + preseq.charAt(sp));

            return new TreeNode(preseq.charAt(sp), null, null);
        } else {
            char rootValue = preseq.charAt(sp);
            int offset = inseq.indexOf(rootValue, si); // This `offset' is a offset to the beginning of string `inseq', so the rest use of this variable must minus the variable `si'.
            TreeNode left = makeTreeAux(sp + 1, sp + offset - si, si, si + offset - si - 1);
            TreeNode right = makeTreeAux(sp + offset - si + 1, ep, si + offset - si + 1, ei);

            return new TreeNode(rootValue, left, right);
        }
    }
}