已知先序遍历和中序遍历，求二叉树的后序遍历

题目

有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。现有两组字母，分别表示前序遍历（父节点->左孩子->右孩子）和中序遍历（左孩子->父节点->右孩子）的结果，请你输出后序遍历（左孩子->右孩子->父节点）的结果。

代码

import java.util.Scanner; // 二叉树节点定义 class TreeNode { char val; TreeNode left; TreeNode right; TreeNode(char v) { val = v; left = null; right = null; } } public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String pre = sc.next(); // 前序 String in = sc.next(); // 中序 TreeNode root = buildTree(pre, in); postOrder(root); } // 根据前序+中序重建二叉树 private static TreeNode buildTree(String pre, String in) { if (pre.isEmpty()) { return null; } // 前序第一个就是根 char rootVal = pre.charAt(0); TreeNode root = new TreeNode(rootVal); // 只有一个节点 if (pre.length() == 1) { return root; } // 在中序里找到根的位置 int midIdx = 0; while (midIdx < in.length() && in.charAt(midIdx) != rootVal) { midIdx++; } // 拆分左右子树 String preLeft = pre.substring(1, midIdx + 1); String preRight = pre.substring(midIdx + 1); String inLeft = in.substring(0, midIdx); String inRight = in.substring(midIdx + 1); root.left = buildTree(preLeft, inLeft); root.right = buildTree(preRight, inRight); return root; } // 后序遍历：左 -> 右 -> 根 private static void postOrder(TreeNode node) { if (node == null) return; postOrder(node.left); postOrder(node.right); System.out.print(node.val); } }