通过后续遍历和中序遍历得到二叉树

Question

后序遍历:CFEGDBJLKIHA
后序遍历:CBEFDGAJIKLH

Answer 1

编程实现？可以参考

package com.renxia;

import sun.reflect.generics.tree.Tree;

import java.util.HashMap;
import java.util.Map;

public class oneZeroSix {
    private static Map<Integer, Integer> inMap;

    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

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

    public  static TreeNode myBuildTree(int[] inorder, int[] postorder, int istart, int iend, int pstart, int pend){
        if(pstart > pend)
            return null;

        int post_root =  pend;
        int in_root = inMap.get(postorder[post_root]);
        int num = in_root - istart;

        TreeNode root = new TreeNode(postorder[post_root]);

        root.left = myBuildTree(inorder, postorder, istart, in_root-1, pstart, pstart+num-1);
        root.right = myBuildTree(inorder, postorder, in_root+1, iend, pstart+num, pend-1);
        return root;
    }

    public static TreeNode buildTree(int[] inorder, int[] postorder){
        int n = inorder.length;
        inMap = new HashMap<>();
        for(int i=0; i < n; i++){
            inMap.put(inorder[i], i);
        }
        return myBuildTree(inorder, postorder, 0, n-1, 0, n-1);
    }

    public static void preOrder(TreeNode root){
        if(root == null)
            return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public static void main(String[] args) {
        int[] inorder = new int[]{9, 3, 15, 20, 7};
        int[] postorder = new int[]{9, 15, 7, 20, 3};
        TreeNode root = buildTree(inorder, postorder);
        preOrder(root);
    }
}