手机端网站 优帮云,外贸网站如何建站,租个国内服务器做网站多少钱,苏州新区建网站题目
给定两个整数数组 preorder 和 inorder #xff0c;其中 preorder 是二叉树的先序遍历#xff0c; inorder 是同一棵树的中序遍历#xff0c;请构造二叉树并返回其根节点。 示例 1: 输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7]
输出: [3,9,20,null,null,1…题目
给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 示例 1: 输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]示例 2:
输入: preorder [-1], inorder [-1]
输出: [-1]提示:
1 preorder.length 3000inorder.length preorder.length-3000 preorder[i], inorder[i] 3000preorder 和 inorder 均 无重复 元素inorder 均出现在 preorderpreorder 保证 为二叉树的前序遍历序列inorder 保证 为二叉树的中序遍历序列 面试中遇到过这道题?
1/5
是
否
通过次数
643.7K
提交次数
899.1K
通过率
71.6%
结点结构
/*** 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:TreeNode* trackback(int l1,int r1,int l2,int r2,vectorint preorder,vectorint inorder){//参数依次为前序遍历的左、右端点中序遍历的左、右端点if(l1r1) return NULL;//找根节点在中序遍历的位置int midl2;while(midr2inorder[mid]!preorder[l1])mid;//构建根节点TreeNode *rootnew TreeNode;root-valpreorder[l1];//递归构建右子树int L1,R1,L2,R2;L1l11;R1l1mid-l2;L2l2;R2mid-1;//cout(L1,R1,L2,R2)\n;root-lefttrackback(L1,R1,L2,R2,preorder,inorder);//递归构建右子树L1R11;R1r1;L2mid1;R2r2;//cout(L1,R1,L2,R2)\n;root-righttrackback(L1,R1,L2,R2,preorder,inorder);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int npreorder.size();TreeNode *roottrackback(0,n-1,0,n-1,preorder,inorder);return root;}
};
