题目描述:
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回二叉树
链接地址:https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
难度:中等
解题思路：
先复习了一下概念
前序遍历：中左右
中序遍历：左中右
后序遍历：左右中
后序遍历从后往前依次为中，在中序遍历中找到对应的位置，该位置的左边构成了左子树，右边构成了右子树，递归调用，直到中序遍历上的指针相遇。
代码：
class Solution {
int index;
public TreeNode buildTree(int[] inorder, int[] postorder) {
index = postorder.length - 1;
return fun(inorder, postorder, 0, inorder.length - 1);
}
private TreeNode fun(int[] inorder, int[] postorder, int start, int end) {
if (start > end) return null;
int val = postorder[index--];
for (int i = start; i <= end; i++) {
if (inorder[i] == val) {
TreeNode root = new TreeNode(val);
root.right = fun(inorder, postorder, i + 1, end);
root.left = fun(inorder, postorder, start, i - 1);
return root;
}
}
return null;
}
}
注意这里的root.right和root.left递归调用顺序不能乱。因为后序遍历从右往左依次存放的是中，右中，右右中等等，从右往左依次拿出了右子树的中数。
分析：
时间复杂度O(NlogN)，空间复杂度O(N)，耗时34 ms。时间又有点长，排名百分之七十。
学习用时最短代码：
public TreeNode buildTree(int[] inorder, int[] postorder) {
return build(inorder, postorder, 0, postorder.length - 1, postorder.length);
}
public TreeNode build(int[] inorder, int[] postorder, int inStart, int postEnd, int length) {
if (length == 0) return null;
int root = postorder[postEnd];
TreeNode treeNode = new TreeNode(root);
if (length == 1) return treeNode;
for (int i = length - 1; i >= 0; i--) {
if (root == inorder[inStart + i]) {
//注意这里的postEnd-length+i不等于i,数组长度变为子数组长度，i的下标已经改变，
//i为左子树长度，在postorder中为左子树于右子树的分界点
treeNode.left = build(inorder, postorder, inStart, postEnd - length + i, i);
treeNode.right = build(inorder, postorder, inStart + i + 1, postEnd - 1, length - 1 - i);
return treeNode;
}
}
return null;
}
只需要2 ms.....他的思路是在后序遍历中找出中值，然后先找左值，最后再找右值。这样做递归调用里面的for循环次数少了很多。所以用时很短。
总结：
二叉树的算法题还是比较薄弱，这思路也是想了很长时间才想到T__T。继续努力！！！
