t****n
发帖数: 19 | 1 死活runtime error啊，在本地调试是可以的啊...囧了，有点怀疑是不是leetcode的问
题了..
Last executed input
[2,1], [2,1]
下面这个实现有什么问题么
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length != postorder.length
|| inorder.length==0){
return null;
}
int rootVal = postorder[postorder.length-1];
int inorderRootPos = Arrays.binarySearch(inorder, rootVal);
TreeNode rootNode = new TreeNode(rootVal);
rootNode.left = buildTree(Arrays.copyOfRange(inorder, 0,
inorderRootPos), Arrays.copyOfRange(postorder, 0, inorderRootPos));
rootNode.right = buildTree(Arrays.copyOfRange(inorder,
inorderRootPos+1, inorder.length), Arrays.copyOfRange(postorder,
inorderRootPos, postorder.length-1));
return rootNode;
}
} | t****n
发帖数: 19 | 2 死活runtime error啊，在本地调试是可以的啊...囧了，有点怀疑是不是leetcode的问
题了..
Last executed input
[2,1], [2,1]
下面这个实现有什么问题么
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length != postorder.length
|| inorder.length==0){
return null;
}
int rootVal = postorder[postorder.length-1];
int inorderRootPos = Arrays.binarySearch(inorder, rootVal);
TreeNode rootNode = new TreeNode(rootVal);
rootNode.left = buildTree(Arrays.copyOfRange(inorder, 0,
inorderRootPos), Arrays.copyOfRange(postorder, 0, inorderRootPos));
rootNode.right = buildTree(Arrays.copyOfRange(inorder,
inorderRootPos+1, inorder.length), Arrays.copyOfRange(postorder,
inorderRootPos, postorder.length-1));
return rootNode;
}
} | c******t
发帖数: 391 | 3 debug了一下，貌似是那个Arrays.BinarySearch的问题，比如BinarySearch([2,1],1)
的结果是-1，因为不是有序的。 换成下面的搜索就可以了：
for(inorderRootPos = 0; inorder[inorderRootPos]!=rootVal; inorderRootPos++);
//empty loop body
my 2 cents :) | g***j
发帖数: 1275 | 4 我这个全部通过了，多半是index的问题
class Solution {
public:
TreeNode *buildTree(vector &inorder, vector &postorder) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(inorder.size() != postorder.size() ||
inorder.size() == 0 || postorder.size() == 0)
return NULL;
return buildTreeHelper(inorder, 0, inorder.size() - 1,
postorder, 0, postorder.size() - 1);
}
TreeNode *buildTreeHelper(vector &inorder, int instart, int inend,
vector &postorder, int poststart, int postend) {
if(instart > inend || poststart > postend) return NULL;
int index = 0;
for(int i = instart; i <= inend; i++) {
if(inorder[i] == postorder[postend]) {
index = i;
break;
}
}
TreeNode* newNode = new TreeNode(postorder[postend]);
newNode->left = buildTreeHelper(inorder, instart, index-1,
postorder,poststart,poststart + index-instart - 1);
newNode->right = buildTreeHelper(inorder, index+1, inend,
postorder, poststart + index -instart, postend - 1);
return newNode;
}
};
【在 t****n 的大作中提到】
: 死活runtime error啊，在本地调试是可以的啊...囧了，有点怀疑是不是leetcode的问
: 题了..
: Last executed input
: [2,1], [2,1]
: 下面这个实现有什么问题么
: public class Solution {
: public TreeNode buildTree(int[] inorder, int[] postorder) {
: if(inorder.length != postorder.length
: || inorder.length==0){
: return null;
| t****n
发帖数: 19 | 5 多谢多谢
自己傻了，怎么会去用BinarySearch..状态不好时真不该去写代码..
);
【在 c******t 的大作中提到】
: debug了一下，貌似是那个Arrays.BinarySearch的问题，比如BinarySearch([2,1],1)
: 的结果是-1，因为不是有序的。 换成下面的搜索就可以了：
: for(inorderRootPos = 0; inorder[inorderRootPos]!=rootVal; inorderRootPos++);
: //empty loop body
: my 2 cents :)
|
|
