Comments (10)
思路:
利用中序把数组划分成左右两个,定出左右子树在中序中的左右界(这里用到哈希表)。前序就好办,挨个遍历就好。有个tricky的地方,就是要保存前序目前处理到哪里了
代码:
class Solution {
private:
int pos = 0;
private:
TreeNode* genTree(vector<int>& pre, unordered_map<int, int>& m, int s, int e) {
if (pos >= pre.size() || s > e) return nullptr;
auto root = new TreeNode(pre[pos++]);
if (s == e) return root;
int loc = m.find(root->val)->second;
root->left = genTree(pre, m, s, loc - 1);
root->right = genTree(pre, m, loc + 1, e);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
auto m = unordered_map<int, int>();
for (auto i = 0; i < inorder.size(); ++i) {
m.insert(make_pair(inorder[i], i));
}
return genTree(preorder, m, 0, inorder.size() - 1);
}
};
from leetcode.
思路:
利用中序把数组划分成左右两个,定出左右子树在中序中的左右界(这里用到哈希表)。前序就好办,挨个遍历就好。有个tricky的地方,就是要保存前序目前处理到哪里了
代码:
class Solution { private: int pos = 0; private: TreeNode* genTree(vector<int>& pre, unordered_map<int, int>& m, int s, int e) { if (pos >= pre.size() || s > e) return nullptr; auto root = new TreeNode(pre[pos++]); if (s == e) return root; int loc = m.find(root->val)->second; root->left = genTree(pre, m, s, loc - 1); root->right = genTree(pre, m, loc + 1, e); return root; } public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { auto m = unordered_map<int, int>(); for (auto i = 0; i < inorder.size(); ++i) { m.insert(make_pair(inorder[i], i)); } return genTree(preorder, m, 0, inorder.size() - 1); } };
非常好。
题一个小优化点:hashmap实际上可以去掉
from leetcode.
var buildTree = function (preorder, inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
if (preorder.length == 1) {
return new TreeNode(preorder[0]);
}
var rn = new TreeNode(preorder[0]); // root node
var rni = inorder.indexOf(preorder[0]); // root node index
rn.left = buildTree(preorder.slice(1, 1 + rni), inorder.slice(0, rni));
rn.right = buildTree(preorder.slice(1 + rni), inorder.slice(rni + 1));
return rn;
};
from leetcode.
var buildTree = function (preorder, inorder) { if (preorder == null || preorder.length == 0) { return null; } if (preorder.length == 1) { return new TreeNode(preorder[0]); } var rn = new TreeNode(preorder[0]); // root node var rni = inorder.indexOf(preorder[0]); // root node index rn.left = buildTree(preorder.slice(1, 1 + rni), inorder.slice(0, rni)); rn.right = buildTree(preorder.slice(1 + rni), inorder.slice(rni + 1)); return rn; };
空间复杂度太高
from leetcode.
var buildTree = function (preorder, inorder) { if (preorder == null || preorder.length == 0) { return null; } if (preorder.length == 1) { return new TreeNode(preorder[0]); } var rn = new TreeNode(preorder[0]); // root node var rni = inorder.indexOf(preorder[0]); // root node index rn.left = buildTree(preorder.slice(1, 1 + rni), inorder.slice(0, rni)); rn.right = buildTree(preorder.slice(1 + rni), inorder.slice(rni + 1)); return rn; };
空间复杂度太高
其实要优化也简单,加几个位置变量就行了。
var buildTree = function (preorder, inorder) {
return temp(0, preorder.length - 1, 0, inorder.length - 1);
function temp(start, end, start2, end2) {
if (start > end) {
return null;
} else if (start == end) {
return new TreeNode(preorder[start]);
}
var rn = new TreeNode(preorder[start]); // root node
var rni = inorder.indexOf(preorder[start], start2); // root node index
rn.left = temp(start + 1, start + rni - start2, start2, rni - 1);
rn.right = temp(start + 1 + rni - start2, end, rni + 1, end2);
return rn;
}
};
from leetcode.
var buildTree = function (preorder, inorder) { if (preorder == null || preorder.length == 0) { return null; } if (preorder.length == 1) { return new TreeNode(preorder[0]); } var rn = new TreeNode(preorder[0]); // root node var rni = inorder.indexOf(preorder[0]); // root node index rn.left = buildTree(preorder.slice(1, 1 + rni), inorder.slice(0, rni)); rn.right = buildTree(preorder.slice(1 + rni), inorder.slice(rni + 1)); return rn; };
空间复杂度太高
其实要优化也简单,加几个位置变量就行了。
var buildTree = function (preorder, inorder) { return temp(0, preorder.length - 1, 0, inorder.length - 1); function temp(start, end, start2, end2) { if (start > end) { return null; } else if (start == end) { return new TreeNode(preorder[start]); } var rn = new TreeNode(preorder[start]); // root node var rni = inorder.indexOf(preorder[start], start2); // root node index rn.left = temp(start + 1, start + rni - start2, start2, rni - 1); rn.right = temp(start + 1 + rni - start2, end, rni + 1, end2); return rn; } };
你的操作好*啊, 还有闭包
from leetcode.
参考答案:
/*
* @lc app=leetcode id=105 lang=javascript
*
* [105] Construct Binary Tree from Preorder and Inorder Traversal
*/
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
function helper(preorder, pStart, pEnd, inorder, iStart, iEnd) {
if (pStart > pEnd || iStart > iEnd) return null;
const root = new TreeNode(preorder[pStart]);
let i = iStart;
while (inorder[i] !== root.val) {
i++;
}
const len = i - iStart;
root.left = helper(preorder, pStart + 1, pStart + len, inorder, iStart, i - 1);
root.right = helper(preorder, pStart + len + 1, pEnd, inorder, i + 1, iEnd);
return root;
}
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function(preorder, inorder) {
// tag: `tree`, `dfs`
if (preorder.length !== inorder.length) return null;
return helper(
preorder,
0,
preorder.length - 1,
inorder,
0,
inorder.length - 1
);
};
from leetcode.
认领
from leetcode.
认领
done
from leetcode.
public class Tree_Reconstruct {
public TreeNode preInToTreeNode(int[] pre,int[] in){
if (pre==null ||in==null){
return null;
}
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < in.length; i++) {
map.put(in[i],i);
}
return PreIn(pre,0,pre.length-1,in,0,in.length-1,map);
}
public TreeNode PreIn(int[] p,int pi,int pj,int[] n,int ni,int nj,HashMap<Integer, Integer> map){
if (pi>pj){
return null;
}
TreeNode node = new TreeNode(p[pi]);
//定义一个中序遍历头节点的索引值
int index=map.get(p[pi]);
node.left=PreIn(p,pi+1,pi+index-ni,n,ni,index-1,map);
node.right=PreIn(p,pi+index-ni+1,pj,n,index+1,nj,map);
return node;
}
}
from leetcode.
Related Issues (20)
- leetcode/thinkings/tree.md 出错 HOT 1
- some error
- 二分查找专题,寻找最左/右插入位置算法模板错误问题 HOT 9
- possible code error in thinkings/heap.md HOT 1
- link error HOT 4
- link is not correct
- [695.最大岛屿面积,360,面试原题]【每日一题】 HOT 3
- 【专题】 反向思考 HOT 3
- 【专题】 考虑每一项对结果到的贡献
- 【专题】递推方程时间复杂度优化
- 已发布文章的代码错误 HOT 7
- Remove duplicate CPP solution and add Python solution for problem 100.same-tree
- Add OSSF Scorecard security workflow
- 题目的排版可否改一改
- 关于二分法中查找中间点索引的算式 HOT 6
- leetcode-thinkings-tree.md BFS 模版调整 HOT 3
- anki-card 中只有10道题吗?截止到2023.11 HOT 1
- 【每日一题】- 2020-xx-xx - xxx
- 大佬,考虑出一个最短路径的专题吗 HOT 8
- leetcode 的anki卡片只有10道题 HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from leetcode.