算法——重建二叉树

重建二叉树（前+中）

问题描述：

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

来源：力扣链接

思路：

根据root节点，将中序vector划分成vin_left，vin_right两部分中序子序列根据中序子序列长度，将前序vector划分成pre_left, pre_right对应的前序子序列

代码：

public TreeNode reConstructBinaryTreeCore(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) { if (preStart > preEnd || inStart > inEnd) { return null; } TreeNode root = new TreeNode(pre[preStart]); int i = inStart; for (; i <= inEnd; i++) { //在中序序列中，找根节点，可以将数组划分为两部分 if (in[i] == pre[preStart]) { //前序的第一个节点，是root，能将中序划分为两部分 // 一棵树，无论前，中，后怎么遍历，元素的个数是不变的 //在实际遍历的时候，前，中，后序遍历，各种遍历方式左右子树的节点都是在一起的 // 所以这里重点是要想清楚下标问题 // 根据中序，我们能确认左子树的节点个数是：i - inStart (没有从0开始哦) // 所以，需要从preStart+1，连续i - inStart个元素，就是左子树的前序序列 root.left = reConstructBinaryTreeCore(pre, preStart + 1, i - inStart + preStart, in, inStart, i - 1); //右子树同理 root.right = reConstructBinaryTreeCore(pre, i - inStart + preStart + 1, preEnd, in, i + 1, inEnd); break; } } return root; } public TreeNode buildTree(int[] pre, int[] in) { if (pre.length == 0 || in.length == 0) { return null; } //理论上，可以新建数组，保存前序，中序子序列，但是就需要花费额外空间 // 所以，我们采取在原数组内进行操作 // 使用闭区间限定数组范围 return reConstructBinaryTreeCore(pre, 0, pre.length-1, in, 0, in.length-1); }

前+中=后

class TreeNode1 { public String data; //数据元素 public TreeNode1 left, right; //指向左，右孩子节点的链 public TreeNode1() { this("?");//将问号做为值传入 } public TreeNode1(String d) { data = d; left = right = null; } public void perorder(TreeNode1 p) {//每一次调用的节点都是根节点 if (p != null) { System.out.print(p.data + " "); perorder(p.left); perorder(p.right); } } public void inorder(TreeNode1 p) { if (p != null) { perorder(p.left); System.out.print(p.data + " "); perorder(p.right); } } public void postorder(TreeNode1 p) { if (p != null) { perorder(p.left); perorder(p.right); System.out.print(p.data + " "); } } } //构造树 class Tree1 { protected TreeNode1 root; public Tree1(String perstr, String instr) { root = enter(perstr, instr); } public void postorderTraversal() { System.out.println("后根遍历"); if (root != null) { root.postorder(root); System.out.println(); } } public TreeNode1 enter(String prestr, String instr) { TreeNode1 p = null; int k, n; String first, presub, insub; n = prestr.length(); if (n > 0) { first = prestr.substring(0, 1); // System.out.println("第一个元素为：" + first); p = new TreeNode1(first); k = instr.indexOf(first); // System.out.println("k在中序遍历中的位置：" + k); presub = prestr.substring(1, k + 1); insub = instr.substring(0, k); p.left = enter(presub, insub); presub = prestr.substring(k + 1, n); insub = instr.substring(k + 1, n); p.right = enter(presub, insub); } return p; } } //测试类 public class s { public static void main(String[] args) { String prestr="ABDGCEFH"; String instr="DGBAECHF"; if(args.length>1){ prestr=args[0]; instr=args[1]; } Tree1 t1=new Tree1(prestr,instr); t1.postorderTraversal(); } }

重建二叉树（中+后）

问题描述：

根据一棵树的中序遍历与后序遍历构造二叉树。

来源：力扣链接

代码：

private int index; public TreeNode buildTree(int[] inorder, int[] postorder) { index = 0; for (int i = 0;i < postorder.length / 2 ; i++) { int temp = postorder[i]; postorder[i] = postorder[postorder.length-1-i]; postorder[postorder.length-1-i] = temp; } return buildTree(postorder,inorder,0,inorder.length); } private TreeNode buildTree(int[] preorder, int[] inorder, int left, int right) { if (left>=right){ return null; } if (index>=preorder.length){ return null; } TreeNode root = new TreeNode(preorder[index]); index++; int pos = find(inorder,left,right,root.val); root.right=buildTree( preorder, inorder, pos + 1, right); root.left=buildTree(preorder,inorder,left,pos); return root; } private int find(int[] inorder, int left, int right, int val) { for (int i = left;i<right;i++){ if (inorder[i]==val){ return i ; } } return -1; }