?哈喽，进来的小伙伴们，你们好耶！?
🍅🍅系列专栏:【强基计划】
????本篇内容:? 根据二叉树的前、中序/中、后序构造二叉树！
??作者简介：一名双非本科大三在读的科班Java编程小白，道阻且长，你我同行！
🍱🍱码云存放仓库gitee：Java数据结构全部代码存放！
一、从前序与中序遍历序列构造二叉树
给定两个整数数组?preorder 和 inorder?，其中?preorder 是二叉树的先序遍历， inorder?是同一棵树的中序遍历，请构造二叉树并返回其根节点。
解题思路：
本题要求我们根据前序遍历和中序遍历来构建这颗二叉树，那么思路非常简单。
1、由前序遍历的第一个节点就是根节点root，首先就得到了根节点。
2、那么得到了根节点，我们就去中序遍历的结果里面找到这个根节点，那么这个root的两侧就是我们的左子树和右子树。
3、定义一个i下标遍历前序的结果，那么这个新的节点就是新的左/右子树的根节点，然后在去中序遍历的结果中找到这个新的根节点，同理，它的两侧就是对应的左/右子树。(递归的思想)
代码实现：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int preIndex = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder,inorder,0,inorder.length-1);
}
private TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {
//1、当前根节点是不是还有左子树 或者 右子树
if(inbegin > inend) {
return null;
}
TreeNode root = new TreeNode(preorder[preIndex]);
//2. 找到root再中序遍历的位置
int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);
preIndex++;
if(rootIndex == -1) {
return null;
}
//3、构建左子树和右子树
root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
return root;
}
private int findIndex (int[] inorder,int inbegin,int inend,int val) {
for(int i = inbegin;i <= inend;i++) {
if(inorder[i] == val) {
return i;
}
}
return -1;
}
}运行结果：
?
?二、从中序与后序遍历序列构造二叉树
解题思路：
那么通过上一题我们已经学会了由前序和中序来构造二叉树，那么同理，由中序和后序来构造二叉树也难不倒你，后序的最后一个节点是根节点，然后在中序遍历中找到这个节点，不过后序我们需要先构造右子树，然后才是左子树，因为后序遍历的顺序是左、右、根！
代码实现：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int postIndex = 0;
public TreeNode buildTree(int[] inorder, int[] postorder) {
postIndex = postorder.length-1;
return buildTreeChild(postorder,inorder,0,inorder.length-1);
}
private TreeNode buildTreeChild(int[] postorder, int[] inorder,int inbegin,int inend) {
//1、当前根节点是不是还有左子树 或者 右子树
if(inbegin > inend) {
return null;
}
TreeNode root = new TreeNode(postorder[postIndex]);
//2. 找到root再中序遍历的位置
int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);
postIndex--;
if(rootIndex == -1) {
return null;
}
//3、构建左子树和右子树
root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
return root;
}
private int findIndex (int[] inorder,int inbegin,int inend,int val) {
for(int i = inbegin;i <= inend;i++) {
if(inorder[i] == val) {
return i;
}
}
return -1;
}
}运行结果：
?