Java 根据一棵树的前序遍历与中序遍历构造二叉树或者根据一棵树的中序遍历与后序遍历构造二叉树

1. 根据一棵树的前序遍历与中序遍历构造二叉树

思路：

遍历前序遍历找到前序遍历的结点在中序遍历当中的位置其左边就是左子树右边就是右子树 更详细的思路在代码块的注释中 public class Tree{ private class Node{ int val; Node left; Node right; public Node(int val) { this.val = val; } } // 根据一棵树的前序遍历与中序遍历构造二叉树 //int[] preorder：前序遍历的数组,int preIndex：前序遍历开始的下标,int[] inorder：中序遍历的数组, // int inbegin：中序遍历的开始,int inend：中序遍历的结束 public int preIndex=0;//开始的下标 public Node buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){//力扣上给的参数不够用，故重新创建了个子函数 if(inbegin>inend){return null;}//没有结点了 //1. 将前序遍历的根结点[即下标为0的地方]作为遍历的开始 Node root=new Node(preorder[preIndex]); //2. 找到当前根节点在中序遍历当中的位置 int rootIndex=findIndexOfInorder(inorder,inbegin,inend,preorder[preIndex]);//前序遍历中的结点在中序遍历的下标 preIndex++; if(rootIndex==-1){ return null; } root.left=buildTreeChild(preorder,inorder,inbegin,rootIndex-1);//左子树 root.right=buildTreeChild(preorder,inorder,rootIndex+1,inend);//右子树 return root; } public int findIndexOfInorder(int[] inorder,int inbegin,int inend,int val){//找到前序遍历中的结点在中序遍历的下标 for(int i=inbegin;i<inend;i++){ if(inorder[i]==val){ return i; } } return -1; } public Node buildTree(int[] preorder,int[] inorder){//构建二叉树 if(preorder==null||inorder==null){ return null; } if(preorder.length<=0||inorder.length<=0){return null;} return buildTreeChild(preorder,inorder,0,inorder.length-1); } } //这篇代码是在力扣上跑过的故只有核心部分，主函数部分就不再呈现。

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

public class Tree{ private class Node{ int val; Node left; Node right; public Node(int val) { this.val = val; } } // 根据一棵树的中序遍历与后序遍历构造二叉树 public int postIndex=0;//开始的下标，在后面的方法中又重新赋值了，该全局变量赋的值被覆盖 public Node buildTreeChild1(int[] inorder,int[] postorder,int inbegin,int inend) {//力扣上给的参数不够用，故重新创建了个子函数 if(inbegin>inend){return null;}//没有结点了 //1. 将后序遍历的根结点[即最后一个元素]作为遍历的开始 Node root=new Node(postorder[postIndex]); //2. 找到当前根节点在中序遍历当中的位置 int rootIndex=findIndexOfInorder1(inorder,inbegin,inend,postorder[postIndex]);//后序遍历中的结点在中序遍历的下标 postIndex--; if(rootIndex==-1){ return null; } root.right=buildTreeChild1(inorder,postorder,rootIndex+1,inend);//右子树 root.left=buildTreeChild1(inorder,postorder,inbegin,rootIndex-1);//左子树 return root; } public int findIndexOfInorder1(int[] inorder,int inbegin,int inend,int val){//找到后序遍历中的结点在中序遍历的下标 for(int i=inbegin;i<=inend;i++){ if(inorder[i]==val){ return i; } } return -1; } public Node buildTree1(int[] inorder,int[] postorder){//构建二叉树 if(inorder==null||postorder==null){ return null; } if(inorder.length<=0||postorder.length<=0){return null;} postIndex=postorder.length-1; return buildTreeChild1(inorder,postorder,0,inorder.length-1); } } //这篇代码是在力扣上跑过的故只有核心部分，主函数部分就不再呈现。