算法伪码(已知树的前序s1,中序遍历s2,求后序遍历s3)

build(int n,int z,int[] s1,int s2[],int[] s3)
if n<=0
// 当前数组的长度为0时退出当前递归
    return;

s3[n+z-1] = s1[0]
//前序的第一位数字,既是后序的当前子树长度+偏移量 位的数字

 int p = searchFirst(lxr, xlr[0]);
//寻找 根节点,在中序中的位置,方便区分左右子树

build(p, z, s1[1,...p+1], s2[0,1...,p], s3);
// 左子树的遍历,左子树长度为p,偏移量不变

build(n - p - 1, z + p, s1[p+1,...], s2[p+1,....],s3);
// 右子树的遍历,右子树长度为n-p-1,偏移量为当前偏移量与左子树长度之和

树的遍历

public class TestB {

    public static void main(String[] args) {
        TestB t = new TestB();

        int[] a = new int[] { 1, 2, 3, 4, 5, 6, 7 };
        TreeNode tree = new TreeNode();
        build(tree, a, 0);
        int[] xlr = new int[] { 1, 2, 5, 3, 6, 7 };
        int[] lxr = new int[] { 2, 5, 1, 6, 3, 7 };
        int[] lrx = new int[6];
        print(tree);
        System.out.println();
        t.build(6, 0, xlr, lxr, lrx);
        t.out(lrx);
    }

    private static class TreeNode {
        Integer val;
        TreeNode parent;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(Integer val) {
            this.val = val;
        }

        void print() {
            System.out.print(this.val + " ");
        }

        @Override
        public String toString() {
            return "TreeNode [val=" + val + ", parent=" + parent + ", left=" + left + ", right=" + right + "]";
        }
    }

    public static void build(TreeNode tree, int[] a, int num) {

        tree.val = a[0];
        tree.left = new TreeNode(a[1]);
        tree.right = new TreeNode(a[2]);

        tree.left.right = new TreeNode(a[4]);
        tree.right.left = new TreeNode(a[5]);
        tree.right.right = new TreeNode(a[6]);

    }

    public static void print(TreeNode tree) {
        if (tree == null) {
            return;
        }

        print(tree.left);

        print(tree.right);
        tree.print();
    }

    /**
     * 
     * @param n 子树数组长度
     * @param z 子树偏移长度
     * @param xlr 前序遍历子树
     * @param lxr 中序遍历子树
     * @param lrx 后续遍历子树
     */
    public void build(int n, int z, int[] xlr, int[] lxr, int[] lrx) {
        if (n <= 0 ) {
            return;
        }
        lrx[n + z - 1] = xlr[0];
        System.out.println(n + " --->  " + z + " --->  " + xlr[0]);
        int p = searchFirst(lxr, xlr[0]);

        // 左子树的遍历
        build(p, z, Arrays.copyOfRange(xlr, 1, p + 1), Arrays.copyOfRange(lxr, 0, p), lrx);

        // 右子树的遍历
        build(n - p - 1, z + p, Arrays.copyOfRange(xlr, p + 1, xlr.length), Arrays.copyOfRange(lxr, p + 1, lxr.length),lrx);
    }

    public int searchFirst(int[] a, int key) {

        for (int i = 0; i < a.length; i++) {
            if (a[i] == key) {
                return i;
            }
        }
        return -1;
    }

    public void out(int[] a) {
        for (int i : a) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}