从中序与后序遍历序列构造二叉树
题目:
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树:
解题思路:和从前序与中序遍历序列构造二叉树相似
/**
* 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 buildTree(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
}
private TreeNode buildTree(int[] inorder, int[] postorder, int inL, int inR, int postL, int postR) {
if(inL > inR || postL > postR)
return null;
int target = postorder[postR];
int cur = inL;
for(int i = cur; i <= inR; i++) {
if(target == inorder[i]) {
cur = i;
break;
}
}
TreeNode node = new TreeNode(target);
//为什么是postR - (inR - cur)
//postR - (inR - cur)是中序数组中右子树部分的长度
node.left = buildTree(inorder, postorder, inL, cur - 1, postL, postR - (inR - cur) - 1);
node.right = buildTree(inorder, postorder, cur + 1, inR, postR - (inR - cur), postR - 1);
return node;
}
}