层序遍历的结果是1、2、3、4、5、6、7、8、9、10、11、12、13、14
构建的树是：
java的代码：
/**
* Copyright (C), 2018-2020
* FileName: build_Tree
* Author: xjl
* Date: 2020/8/2 14:42
* Description: 构造二叉树
*/
package Tree;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class build_Tree {
private static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* 根据层序前序的结果构建二叉树
*
* @param treedata
* @param n
* @return
*/
public static TreeNode BuildTree(int[] treedata, int n) {
if (treedata.length == 0)
return null;
else {
if (n < treedata.length) {
int l = n * 2 + 1;
int r = n * 2 + 2;
TreeNode TreeRoot = new TreeNode(treedata[n], BuildTree(treedata, l), BuildTree(treedata, r));
return TreeRoot;
} else
return null;
}
}
//前序
public static List before(TreeNode root) {
List list = beforetest(root, new ArrayList());
return list;
}
/**
* 前序遍历的是的 根左右
*
* @param root
* @param list
* @return
*/
public static List beforetest(TreeNode root, List list) {
if (root == null) {
return null;
}
list.add(root.val);
if (root.left != null) {
beforetest(root.left, list);
}
if (root.right != null) {
beforetest(root.right, list);
}
return list;
}
//中序
public static List mid(TreeNode root) {
List reslut = midtest(root, new ArrayList());
return reslut;
}
/**
* 中序遍历是左根右
*
* @param root
* @param list
* @return
*/
public static List midtest(TreeNode root, List list) {
if (root == null) {
return null;
}
if (root.left != null) {
beforetest(root.left, list);
}
list.add(root.val);
if (root.right != null) {
beforetest(root.right, list);
}
return list;
}
//后序
public static List after(TreeNode root) {
List list = aftertest(root, new ArrayList());
return list;
}
/**
* 后序遍历左右根
*
* @param root
* @param list
* @return
*/
public static List aftertest(TreeNode root, List list) {
if (root == null) {
return null;
}
if (root.left != null) {
beforetest(root.left, list);
}
if (root.right != null) {
beforetest(root.right, list);
}
list.add(root.val);
return list;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String tempdata = sc.nextLine();
String[] data = tempdata.split(" ");
TreeNode treeroot;
int[] treedata = new int[data.length];
for (int i = 0; i < treedata.length; i++) {
treedata[i] = Integer.parseInt(data[i]);
}
treeroot = BuildTree(treedata, 0);
List before = before(treeroot);
List mid = mid(treeroot);
List after = after(treeroot);
//结果的输出
System.out.print("前序遍历=");
for (int V : before) {
System.out.print(V + " ");
}
System.out.println();
System.out.print("中遍历=");
for (int V : mid) {
System.out.print(V + " ");
}
System.out.println();
System.out.print("后遍历=");
for (int V : after) {
System.out.print(V + " ");
}
System.out.println();
}
}
java的代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
//输入的是前序遍历的结果 中序遍历的结果
public TreeNode buildTree(int[] preorder, int[] inorder) {
//递归函数的出口是
if (preorder == null || preorder.length == 0) {
return null;
}
//获取到根节点的value的值
TreeNode root = new TreeNode(preorder[0]);
//构建left right子树
int index = findIndex(preorder, inorder);
// root.left = buildTree( 左子树的前序数组 左子树的中序数组);
root.left = buildTree(Arrays.copyOfRange(preorder, 1, index+1), Arrays.copyOfRange(inorder, 0, index));
//root.right = buildTree(右子树的前序数组 右子树的中序数组);
root.right = buildTree(Arrays.copyOfRange(preorder, index + 1, preorder.length), Arrays.copyOfRange(inorder, index + 1, inorder.length));
return root;
}
//为了找到中序遍历的过程中位置
private int findIndex(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == preorder[0]) {
return i;
}
}
return 0;
}
}
Java的代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return getNode(inorder, postorder, 0, inorder.length - 1, inorder.length - 1);
}
/**
* 获取节点
* 中序：左->根->右
* 后序：左->右->根
*
* 根据规律:通过后序找到根节点，通过中序分辨左右
* 实现方式：使用三个指针分别记录中序的开始到结束，及其中根节点在后序中的位置
* 原始：中序开始instart(0),中序结束inend(len-1),后序postend(len-1)；
* 找到中序根位置index,此时我们可以知道：
* - 左子树（0，index),根->新postend(原postend-右子树长度（inend-index)-自己（1）），此时获取左子树的根节点就是当前根节点的左节点
* - 右子树（index+1,inend),根->新postend(原postend-1)
*
* @param inorder 中序数组
* @param postorder 后序数组
* @param instart 中序开始指向
* @param inend 中序结束指向
* @param postend 指向根节点在后序数组的下标
* @return TreeNode
*/
public TreeNode getNode(int[] inorder, int[] postorder, int instart, int inend, int postend) {
// 结束条件，开始大于结束
if (instart > inend) {
return null;
}
// 节点值
int nodeVal = postorder[postend];
// 当前节点
TreeNode node = new TreeNode(nodeVal);
// 节点中中序数组中的下标
int nodeIndex = 0;
for (int i = instart; i 新postend(原postend-右子树长度（inend-index)-自己（1））
node.left = getNode(inorder, postorder, instart, nodeIndex - 1, postend - (inend - nodeIndex) - 1);
// 右子树（index+1,inend),根->新postend(原postend-1)
node.right = getNode(inorder, postorder, nodeIndex + 1, inend, postend - 1);
return node;
}
}
