网站开发项目实训总结,wordpress 评论优化,乐清网站建设,配资网站建设多少钱题目
输入一棵二叉树前序遍历和中序遍历的结果#xff0c;请重建该二叉树。
注意:二叉树中每个节点的值都互不相同#xff1b;输入的前序遍历和中序遍历一定合法#xff1b;样例
给定#xff1a;
前序遍历是#xff1a;[3, 9, 20, 15, 7]
中序遍历是#xff1a;[9, 3, …题目
输入一棵二叉树前序遍历和中序遍历的结果请重建该二叉树。
注意:二叉树中每个节点的值都互不相同输入的前序遍历和中序遍历一定合法样例
给定
前序遍历是[3, 9, 20, 15, 7]
中序遍历是[9, 3, 15, 20, 7]返回[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示3/ \9 20/ \
15 7方法一
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {public:unordered_mapint, int pos;TreeNode* buildTree(vectorint preorder, vectorint inorder) {int ninorder.size();for(int i0; in; i) {pos[inorder[i]]i;}return dfs(preorder, inorder, 0, n-1, 0, n-1);}TreeNode* dfs(vectorint preorder, vectorint inorder, int pl, int pr, int il, int ir) { //pl、pr表示的是前序遍历的左右指针指向第一和最后元素//il和il相同if((pl pr) (il ir)) return NULL;int kpos[preorder[pl]] - il; //由于pos表示的inorder中各个元素位置所以这里的k是根节点左侧有多少个元素。TreeNode* root new TreeNode(preorder[pl]);root-left dfs(preorder, inorder, pl1, plk, il, ilk-1); root-right dfs(preorder, inorder, plk1, pr, ilk1, ir);return root;}};心得 中心在于转化为个数个数联动了前序和后序遍历。 而后面 root-left dfs(preorder, inorder, pl1, plk, il, ilk-1); root-right dfs(preorder, inorder, plk1, pr, ilk1, ir);便是基于个数而写出的。 根节点左子树前序是从pl1到plk的数同理左子树中序和右子树。
