2020-09-07 通过二叉树的先序和中序遍历结果求后序遍历结果

代码实现：
/*
public class TreeNode {
    String value;
    TreeNode left;
    TreeNode right;
    TreeNode(String x) { value = x; }
}
 */
import java.util.HashMap;
/**
 * @Author: deemoHui
 * @Description: 根据二叉树的先序遍历和中序遍历求后序遍历
 * @Date Created in 2020-09-07 10:50
 * @Modified By:
 */
public class PreInToPost{
    public static void main(String[] args) {
        String[] preorder = new String[]{"A","D","C","E","F","G","H","B"};
        String[] inorder = new String[]{"C","D","F","E","G","H","A","B"};
        TreeNode root = new BuildTree().buildTree(preorder, inorder);
        System.out.print("后序遍历结果：");
        postOrder(root);
    }
    public static void postOrder(TreeNode node){
        if(node==null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.value);
    }
}
class BuildTree {
    HashMap<String, Integer> map = new HashMap<>();
    String[] po;
    public TreeNode buildTree(String[] preorder, String[] inorder) {
        po = preorder;
        for(int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return recur(0, 0, inorder.length - 1);
    }
    TreeNode recur(int pre_root, int in_left, int in_right) {
        if(in_left > in_right) {
            return null;
        }
        TreeNode root = new TreeNode(po[pre_root]);
        int i = map.get(po[pre_root]);
        root.left = recur(pre_root + 1, in_left, i - 1);
        root.right = recur(pre_root + i - in_left + 1, i + 1, in_right);
        return root;
    }
}

更好的解释见：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-di-gui-fa-qin/