欢迎访问LeetCode题解合集
题目描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
题解:
前序遍历:根节点 左子树 右子树
中序遍历:左子树 根节点 右子树
所以,可以根据先序遍历得到根节点,然后在中序遍历序列中找到根节点位置 p
,p
的左边就是左子树的中序遍历序列,p
的右边就是右子树的中序遍历序列。
递归生成左右子树即可。
时间复杂度:$O(n^2)$
额外空间复杂度:$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void build( TreeNode*& root, int l1, int r1, int l2, int r2, vector<int>& preorder, vector<int>& inorder ) {
if ( l1 > r1 ) return;
int p, len;
for ( p = l2; p <= r2 && inorder[p] != preorder[l1]; ++p );
len = p - l2;
root = new TreeNode( preorder[l1] );
build( root->left, l1 + 1, len + l1, l2, p - 1, preorder, inorder );
build( root->right, len + l1 + 1, r1, p + 1, r2, preorder, inorder );
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
TreeNode *root = nullptr;
build ( root, 0, preorder.size() - 1, 0, preorder.size() - 1, preorder, inorder );
return root;
}
};
/*
时间:36ms,击败:43.11%
内存:24.6MB,击败:42.04%
*/
可以使用一个哈希表记录 中序遍历 序列中每个值的位置,在递归建树过程中省掉遍历的步骤。
时间复杂度:$O(n)$
额外空间复杂度:$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
unordered_map<int, int> hash;
void build( TreeNode*& root, int l1, int r1, int l2, int r2, vector<int>& preorder, vector<int>& inorder ) {
if ( l1 > r1 ) return;
int p = hash[preorder[l1]];
int len = p - l2;
root = new TreeNode( preorder[l1] );
build( root->left, l1 + 1, len + l1, l2, p - 1, preorder, inorder );
build( root->right, len + l1 + 1, r1, p + 1, r2, preorder, inorder );
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
TreeNode *root = nullptr;
for ( int i = 0; i < inorder.size(); ++i )
hash[inorder[i]] = i;
build ( root, 0, preorder.size() - 1, 0, preorder.size() - 1, preorder, inorder );
return root;
}
};
/*
时间:20ms,击败:80.26%
内存:25MB,击败:40.15%
*/