二叉树 java（哔站解法） 一个方法解决 已知前序中序 或后序中序 或层序中序，求其他序输出

此解法逻辑来源于哔站大佬，先上视频：

无脑秒解！已知先/后序遍历与中序遍历，求后/先序遍历。_哔哩哔哩_bilibili大佬轻喷，这个题做很简单，但是想做的快做的准应该没有比这更快的了。原理是什么，问就是不知道，你们看我这破书是20年的就应该知道我是菜鸡了。随便找几个题试一下我保证你对。https://www.bilibili.com/video/BV1Xu411d7qf?spm_id_from=333.999.0.0

这个方法神奇就在于，y轴适用于 前序，后序（倒过来写），层序。一行代码都不用改的情况下，可以解三种题！

下面是我按照整个图表解题的思路，实现的java代码：

import java.util.*;

public class DemoShu {
	// 已知前序中序求后序
	public static void main(String[] args) {
		String qian = "ABCDEFGHIJ";// 前序
		String mid = "CBAFEDIHJG";// 中序
		// 已知前序中序建树
		TreeNode geng = new TreeNode(qian.substring(0, 1));// 已知前序第一位是根
		jianShu(geng, null, null, qian, mid);// 建树
		// 解析树并输出
		List list = new ArrayList<>();
		houxu(geng, list);// 后序输出
		System.out.println(list.toString());
	}

	
	public static void jianShu(TreeNode tn, Integer leftBian, Integer rightBian, String qianStr, String midStr) {
		int tnQianIndex = qianStr.indexOf(tn.data);// 根在前序字符串中的位置
		int tnMidIndex = midStr.indexOf(tn.data);// 根在中序字符串中的位置
		// 找左子树 在根的左下方
		for (int i = tnQianIndex + 1; i < qianStr.length(); i++) {// 在前序字符串中从上往下找
			int indexOfMid = midStr.indexOf("" + qianStr.charAt(i));// 这个字符在中序字符串中的位置
			if (indexOfMid < tnMidIndex) {// 如果在根的左边
				if (leftBian != null) {// 有左边界，则要同时满足在左边界的右边
					if (leftBian < indexOfMid) {
						TreeNode leftTN = new TreeNode("" + qianStr.charAt(i));// 找到左子树
						tn.left = leftTN;
						// 将该左子树带入递归当做根，找它的子树，它的子树的左边界是它的原有左边界
						// 它的子树的右边界是它的根在中序字符串中的位置
						// ps：这里为什么有左边界，思考下，那肯定是因为它的根的某个根，是个右子树
						jianShu(leftTN, leftBian, tnMidIndex, qianStr, midStr);
						break;
					}
				} else {
					TreeNode leftTN = new TreeNode("" + qianStr.charAt(i));// 找到左子树
					tn.left = leftTN;
					jianShu(leftTN, null, tnMidIndex, qianStr, midStr);
					break;
				}
			}
		}
		// 找右子树 在根的右下方，注解和左子树差不多，略。
		for (int i = tnQianIndex + 1; i < qianStr.length(); i++) {
			int indexOfMid = midStr.indexOf("" + qianStr.charAt(i));
			if (indexOfMid > tnMidIndex) {// 如果在根的右边
				if (rightBian != null) {// 有右边界，则要同时满足在右边界的左边
					if (rightBian > indexOfMid) {
						TreeNode rightTN = new TreeNode("" + qianStr.charAt(i));
						tn.right = rightTN;
						jianShu(rightTN, tnMidIndex, rightBian, qianStr, midStr);
						break;
					}
				} else {
					TreeNode rightTN = new TreeNode("" + qianStr.charAt(i));
					tn.right = rightTN;
					jianShu(rightTN, tnMidIndex, null, qianStr, midStr);
					break;
				}
			}
		}
		return;
	}

	// 前序遍历输出
	public static void qianxu(TreeNode tn, List list) {
		if (tn == null) {
			return;
		}
		list.add(tn.data);
		qianxu(tn.left, list);
		qianxu(tn.right, list);
	}

	// 中序遍历输出
	public static void zhongxu(TreeNode tn, List list) {
		if (tn == null) {
			return;
		}
		zhongxu(tn.left, list);
		list.add(tn.data);
		zhongxu(tn.right, list);
	}

	// 后序遍历输出
	public static void houxu(TreeNode tn, List list) {
		if (tn == null) {
			return;
		}
		houxu(tn.left, list);
		houxu(tn.right, list);
		list.add(tn.data);
	}

	// 层序遍历输出
	public static void cengxu(List treeNodes, List list) {
		if (treeNodes.size() > 0) {
			ArrayList tns = new ArrayList();
			for (TreeNode tn : treeNodes) {
				list.add(tn.data);
				if (tn.left != null) {
					tns.add(tn.left);
				}
				if (tn.right != null) {
					tns.add(tn.right);
				}
			}
			cengxu(tns, list);
		} else {
			return;
		}

	}

	static class TreeNode {
		String data;
		TreeNode left;
		TreeNode right;

//		public TreeNode() {
//			super();
//		}

		public TreeNode(String data) {
			super();
			this.data = data;
		}

		public TreeNode(String data, TreeNode left, TreeNode right) {
			super();
			this.data = data;
			this.left = left;
			this.right = right;
		}

	}

}

jianShu()方法就是通过前+中 or 后+中 or 层+中 生成二叉树。

生成二叉树后，我们可以有四种遍历方法去输出（也在代码中总结了），入参都是根节点。