题目概述(中等难度)
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3 / \ 9 20 / \ 15 7
题目链接：
点我进入leetcode
思路与代码
这道题目的思路与我们前序和中序构造二叉树的思路是一样的，这次是给了我们后序遍历的结果，我们的后序遍历的结果也是可以寻找到我们的根节点的，因为后序遍历的方式是左右根，而又因为中序遍历的方式为左根右，所以当我们使用preIndex遍历到我们的根节点的时候，应该首先构建的是我们的右子树，再构建我们的左子树.
下面我把前序和中序构造二叉树的博客放到这里：核心思路是一样的，在这里我就不再做过多的赘述:
点我进入博客
代码示例
class Solution { //postIndex为后序遍历的下标,用于遍历后序遍历的结果 public int postIndex = 0; public TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend) { //说明没有左树或者没有有树,递归的终止条件 if(inbegin > inend) { return null; } //创建根节点 TreeNode root = new TreeNode(postorder[postIndex]); //在中序遍历的数组当中，找到当前根节点所在位置,此处我们需要额外定义一个findValInorder方法 int index = findValInorder(inorder,postorder[postIndex],inbegin,inend); postIndex--; //使用递归遍历来创建左树和右树 //注意此处是先创建右树再创建左树 root.right = buildTreeChild(postorder,inorder,index+1,inend); root.left = buildTreeChild(postorder,inorder,inbegin,index-1); return root; } //此方法用于返回当前根节点在中序遍历结果中的位置，key为我们当前根节点的val值 public int findValInorder(int[] inorder,int key,int inbegin,int inend) { //注意是小于等于 for(int i = inbegin;i <= inend;i++) { if(inorder[i] == key) { return i; } } //没找到返回-1 return -1; } public TreeNode buildTree(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 buildTreeChild(postorder,inorder,0,inorder.length - 1); } }
时间复杂度:O(N)
空间复杂度:O(N）
总结
一般来说我们可以根据前序和中序构造二叉树，可以根据中序和后序来构造二叉树，但是不能根据前序和后序来构造二叉树，因为前序和中序都可以确定我们的根节点，那么由谁来确定我们的左树和右树呢？所以必须包含我们的中序遍历的结果来确定我们的左树和右树.
