我最近一直在研究leetcode,并困惑为什么我将解决方案提交给Leetcode时会超时。
这里是问题:
https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/942/
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
这是我的解决方案,其中一个测试用例超时:
/**
* 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) {
if (inorder == null || inorder.length == 0) {
return null; // input error
}
if (postorder == null || postorder.length == 0) {
return null; // input error
}
if (postorder.length != inorder.length) {
return null; // input error
}
List<Integer> inOrder = new ArrayList<Integer>();
List<Integer> postOrder = new ArrayList<Integer>();
for (int i = 0; i < inorder.length; i++) {
inOrder.add(inorder[i]);
postOrder.add(postorder[i]);
}
return buildBinaryTree(inOrder, postOrder);
}
public TreeNode buildBinaryTree(List<Integer> inOrder, List<Integer> postOrder) {
boolean found = false;
int root = 0;
int rootIndex = 0;
// for given in-order scan the post-order right to left to find the root
for (int j = postOrder.size() - 1; j >= 0 && !found; j--) {
root = postOrder.get(j);
if (inOrder.contains(root)) {
rootIndex = inOrder.indexOf(root);
root = inOrder.get(rootIndex);
found = true;
break;
}
}
if (found) {
List<Integer> leftOfRoot = new ArrayList<Integer>();
List<Integer> rightOfRoot = new ArrayList<Integer>();
if (rootIndex > 0) {
leftOfRoot.addAll(inOrder.subList(0, rootIndex));
}
if ((rootIndex + 1) < inOrder.size()) {
rightOfRoot.addAll(inOrder.subList(rootIndex + 1, inOrder.size()));
}
TreeNode node = new TreeNode(root);
node.left = buildBinaryTree(leftOfRoot, postOrder);
node.right = buildBinaryTree(rightOfRoot, postOrder);
return node;
}
return null;
}
}
任何人都可以帮助确定为什么会这样吗?我认为这是Leetcode法官的过错,我的代码很好。
Leetcode的判断可能还可以。此代码对于嵌套线性数组操作和堆分配太随意了。创建ArrayList
并调用contains
,addAll
,subList
和indexOf
可能看起来是无害的,但是当它们在递归函数中时会被认为是极其昂贵的操作,该函数在每一帧中产生两个子调用。
让我们稍微解压代码:
List<Integer> inOrder = new ArrayList<Integer>();
List<Integer> postOrder = new ArrayList<Integer>();
for (int i = 0; i < inorder.length; i++) {
inOrder.add(inorder[i]);
postOrder.add(postorder[i]);
}
这是一笔很小的前期费用,但这是未来的预兆。我们已经完成了2个不必要的堆分配,并且遍历了整个n
。我只是在这里坚持原始数组,我们不需要分配除结果节点以外的对象。
接下来,我们进入buildBinaryTree
,这是一个昂贵的递归函数,即使它在体内没有任何作用。结构本质上是这样的:
function buildBinaryTree(root) {
// do some stuff
if (not base case reached) {
buildBinaryTree(root.left)
buildBinaryTree(root.right)
}
}
此算法的时间复杂度是指数级的,因此,// do some stuff
精简且高效,希望是恒定的时间,[[非常很重要,但是最坏的情况下,我们可以容忍线性系数低的情况。
for (int j = postOrder.size() - 1; j >= 0 && !found; j--) {
root = postOrder.get(j);
if (inOrder.contains(root)) {
rootIndex = inOrder.indexOf(root);
这看起来是二次的,但实际上,根据定义,在第一次迭代中会发现root
,因为根始终是后序遍历数组中的最后一个元素。但是仅在之后立即调用contains
才调用indexOf
是没有意义的;您可以直接使用indexOf
,而无需调用contains
。代码:
if (found) { List<Integer> leftOfRoot = new ArrayList<Integer>(); List<Integer> rightOfRoot = new ArrayList<Integer>();
对每个调用帧进行更多不必要的堆分配。这里,
leftOfRoot.addAll(inOrder.subList(0, rootIndex));
遍历列表两次,一次创建子列表,再一次将整个子列表添加到ArrayList
。对右边的子树再次重复。同样,这些都是嵌套工作,这是不必要的。每个调用帧使用start
和end
索引意味着您无需分配堆内存或将任何内容从一个堆栈帧复制到下一帧。只需更改开始/结束索引并在整个时间内将引用传递给相同的两个数组。我建议使用分析器运行您的代码,以准确了解复制和扫描
ArrayList
所花费的时间。正确的实现最多应该在每个调用帧中浏览一个列表(搜索将尽早解决,因此实际上是次线性的)。