算法伪码(已知树的前序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();    }}