class Solution:
def deduceTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
hmap,preorder = {}, preorder
for i in range(len(inorder)):
hmap[inorder[i]] = i
def recur(root,left,right):
if left > right:return
node = TreeNode(preorder[root])
i = hmap[preorder[root]] #根据pre里面的root节点位置找inorder的顺序划分左右子树
node.left = recur(root+1,left,i-1)
node.right = recur(root+i-left+1,i+1,right)
return node
return recur(0,0,len(inorder)-1)
shuaidi
共以下 27 个回答
Map< Integer, Integer > map = new HashMap();
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder null || preorder.length <= 0){
return null;
}
// 简历中序遍历数组的映射（就是为了快速求出某个元素的下标）
for(int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
思路：前序遍历第一个值即为父节点，然后在中序遍历中找到父节点，其左边的值为左子树，右边的值为右子树，然后递归的建立二叉树。
“`c++& preorder, int prel, int prer, vector & inorder, int inl, int inr) { & preorder, vector & inorder) {
class Solution {
public:
TreeNode* GeneTree(vector
if (prel > prer) return nullptr;
TreeNode* root = new TreeNode(preorder[prel]);
int mid = inl;
while (mid <= inr && inorder[mid] != preorder[prel]) mid++; root->left = GeneTree(preorder, prel+1, prel+mid-inl, inorder, inl, mid-1);
root->right = GeneTree(preorder, prel+mid-inl+1, prer, inorder, mid+1, inr);
return root;
}
TreeNode* deduceTree(vector
return GeneTree(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
}
};
“`
class Solution {
}
忘了还有哈希表建立索引，
时间复杂度 O(N) ： 其中 NN 为树的节点数量。初始化 HashMap 需遍历 inorder ，占用 O(N) 。递归共建立 NN 个节点，每层递归中的节点建立、搜索操作占用 O(1) ，因此使用 O(N) 时间。
空间复杂度 O(N) ： HashMap 使用 O(N) 额外空间；最差情况下（输入二叉树为链表时），递归深度达到 N ，占用 O(N)的栈帧空间；因此总共使用 O(N) 空间。
~~~java
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
//用hashmap记录inorder可以减少递归中的循环带来的消耗
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
}
java
时间复杂度 O(N) ： 其中 NN 为树的节点数量。初始化 HashMap 需遍历 inorder ，占用 O(N) 。递归共建立 NN 个节点，每层递归中的节点建立、搜索操作占用 O(1) ，因此使用 O(N) 时间。
空间复杂度 O(N) ： HashMap 使用 O(N) 额外空间；最差情况下（输入二叉树为链表时），递归深度达到 N ，占用 O(N)的栈帧空间；因此总共使用 O(N) 空间。
Day9 有点难度。。
分治思想重置二叉树
class Solution {& preorder, vector & inorder) {
private:
unordered_map<int,int> myMap;
public:
TreeNode* deduceTree(vector
};
递归，难点是计算左右子树的开始和结束位置
day9第一题
时间复杂度 O(N) ,空间复杂度 O(N)
重建二叉树java
时空复杂度O(N)
使用递归的方法实现
类似归并排序的分治递归方法
时间复杂度$O(n)$，空间复杂度$O(n)$
HashMap<Integer, Integer> map = new HashMap<>();//标记中序遍历
int[] preorder;//保留的先序遍历，方便递归时依据索引查看先序遍历的值
public TreeNode deduceTree(int[] preorder, int[] inorder) {
this.preorder =preorder;
for(int i=0;i<inorder.length;i++){
hmap.put(inorder[i],i);
}
return recur(0,0,inorder.length-1);
}
TreeNode recur(int root,int left,int right){
if(left>right) return null;
TreeNode node =new TreeNode(preorder[root]);
int i=hmap.get(preorder[root]);
node.left =recur(root+1,left,i-1);
node.right=recur(root+i-left+1,i+1,right);
return node;
}
需要再理解
没想到有一天我也能一次AC哈哈
https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/solutions/2679862/gou-zao-er-cha-shu-by-yukislab-7jsx
打卡
Definition for a binary tree node.
class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def deduceTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
hmap,preorder = {}, preorder
for i in range(len(inorder)):
hmap[inorder[i]] = i
双on 第一个参数的root是preorder的位置，永远根据preorder找根节点。left和right是在inorder的位置。
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
#include
#include
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param preOrder int整型vector
* @param vinOrder int整型vector
* @return TreeNode类
*/
private: preOrder;
vector
unordered_map<int, int> map;
TreeNode* recur(int root, int left, int right){
if(left > right) return nullptr;//边界条件
TreeNode* node = new TreeNode(preOrder[root]);//构建头节点
int bound = map[preOrder[root]];//找到分界点
node->left = recur(root + 1, left, bound – 1);
node->right = recur(root + bound -left + 1, bound + 1, right);
return node;
}
};
class Solution {
private HashMap<Integer,Integer> inorderPosition;
public TreeNode deduceTree(int[] preorder, int[] inorder) {
inorderPosition = new HashMap<>();
for(int i = 0; i < inorder.length; i++){
inorderPosition.put(inorder[i],i);
}
return rec(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
private TreeNode rec(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2){
if(l1 > r1 || l2 > r2)
return null;
TreeNode root = new TreeNode(preorder[l1]);
int i = inorderPosition.get(preorder[l1]);
root.left = rec(preorder,l1+1,l1+i-l2,inorder,l2,i-1);
root.right = rec(preorder,r1-r2+i+1,r1,inorder,i+1,r2);
return root;
}
}
//使用递归算法 时间复杂度On 空间复杂度On
思路是看了题解才会的，用哈希表储存节点编号和中序遍历的关系然后递归中用先序找出头节点的编号
时间复杂度O(n)
空间复杂度O(n)
“`C++& preorder, vector & inorder) { preorder;
class Solution {
public:
TreeNode* deduceTree(vector
if(preorder.empty() == true || inorder.empty() == true)
{
return nullptr;
}
this->preorder = preorder;
for(int i = 0; i < inorder.size(); i++) { submap[inorder[i]] = i; } return build(0, 0, inorder.size() - 1); } private: vector
unordered_map<int,int> submap;
//第一个参数用于利用前序遍历来确定节点在中序遍历中的位置
//第二、三个参数用于判断递归是否满足结束条件
TreeNode* build(int root, int left, int right)
{
//递归终止条件
if (left > right)
{
return nullptr;
}
//建立根节点
TreeNode* node = new TreeNode(preorder[root]);
//划分左、中、右子树,i为中序遍历的中间节点
int i = submap[preorder[root]];
//递归左子树
node->left = build(root + 1, left, i – 1);
//递归右子树
node->right = build(root + i – left + 1, i + 1, right);
};
“`