1、题目
image.png2、分析
这道题的做法和第105题:从中序与前序遍历序列构造二叉树。一样的解法。
只要找到中序遍历和后序遍历的规则,关键是找出迭代的索引位置就可以了。
3、代码
/**
* 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 TreeNode buildTree(int[] inorder, int[] postorder) {
return build(inorder, 0, inorder.length - 1,
postorder, 0, postorder.length - 1);
}
private TreeNode build(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd){
if (postStart > postEnd){
return null;
}
int index = -1;
int rootVal = postorder[postEnd];
for (int i = inStart; i <= inEnd; i++){
if (inorder[i] == rootVal){
index = i;
break;
}
}
int rightSize = inEnd - index;
TreeNode root = new TreeNode(rootVal);
root.left = build(inorder, inStart, index - 1,
postorder, postStart, postEnd - rightSize - 1);
root.right = build(inorder, index + 1, inEnd,
postorder, postEnd - rightSize, postEnd - 1);
return root;
}
}
网友评论