返回信息流问题: Construct Binary Tree from Preorder and Inorder Traversal
lc上大神的算法如下, 既简洁又快速, 但是大佬们能解释一下这个算法是怎么想到的吗? 为什么能想到能用inindex++ 来 控制递归出口 ? 这个符合了先序和中序遍历的那个特点才能想到啊?
public TreeNode buildTree(int[] pre, int[] in) {
if (pre == null || in == null || pre.length == 0 || in.length == 0 || pre.length != in.length) {
return null;
}
inIndex = 0;
preIndex = 0;
return helper(pre, in, Integer.MAX_VALUE);
}
private TreeNode helper(int[] pre, int[] in, int root) {
if (inIndex == in.length || in[inIndex] == root) {
return null;
}
TreeNode cur = new TreeNode(pre[preIndex++]);
cur.left = helper(pre, in, cur.val);
inIndex++;
cur.right = helper(pre, in, root);
return cur;
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #93157同步于 2017/5/8
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
lc 一道题求解释
heygirl
2017/5/8镜像同步6 回复
订阅后，新回复会通过你的通知中心匿名送达。
6 条回复
感谢回复, 你的这个方法我明白, 不是最优的, 因为在递归里还有for-loop, 和我的问题不一样啊, 我百度了, 这个方法没找到解释, 您可以在看看我的方法, 时间和空间都是最优的~, 看明白了希望可以讲解一下
【 在 whn6325689 的大作中提到: 】
: http://www.cnblogs.com/springfor/p/3884034.html
: 我猜，百度一下就可以了？
这种打法跑起来一点问题都没有,但就是不知道是怎么想出来的。
那个2ms用栈的打法也一样。
【 在 heygirl 的大作中提到: 】
: 感谢, 你也有同样的问题吗?