国内精美网站界面网址,惠州品牌网站建设价格,深圳市凡客创品科技有限公司,kocool网站开发目录
1、题目链接
2、题目介绍
3、解法
函数头-----找出重复子问题
函数体---解决子问题
4、代码 1、题目链接
105.从前序与中序遍历序列构造二叉树. - 力扣#xff08;LeetCode#xff09; 2、题目介绍
3、解法 前序遍历性质#xff1a; 节点按照 [ 根节点 …目录
1、题目链接
2、题目介绍
3、解法
函数头-----找出重复子问题
函数体---解决子问题
4、代码 1、题目链接
105.从前序与中序遍历序列构造二叉树. - 力扣LeetCode 2、题目介绍
3、解法 前序遍历性质 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序。 中序遍历性质 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。 因此我们可以利用前序确定二叉树的根节点中序遍历确定左、右子树的结点数。 前序遍历的首元素 为 树的根节点 node 的值。在中序遍历中搜索根节点 node 的索引 可将 中序遍历 划分为 [ 左子树 | 根节点 | 右子树 ] 。根据中序遍历中的左右子树的节点数量可将 前序遍历 划分为 [ 根节点 | 左子树 | 右子树 ] 。 函数头-----找出重复子问题 重复子问题前序构建二叉树。根节点、左子树根节点、右子树根节点 参数 根节点在前序遍历的索引 root 、子树在中序遍历的左边界 left 、子树在中序遍历的右边界 right 函数体---解决子问题 1、构建根节点、 2、找出根节点在中序遍历中对应的下标 i 利用哈希表进行辅助划分左、右子树 3、构建左子树更新参数root、left、right 4、构建右子树更新参数root、left、right 4、代码 class Solution {public:unordered_mapint, int hash; //哈希表便于寻找inorder中根节点的下标//参数: 前序根节点对应的在前序的下标左子树起始位置(中序)右子树结束位置中序TreeNode* dfs(const vectorint preorder, int root, int left, int right) {if (left right)//左右子树都为空{return NULL;}//构建根节点TreeNode* BTroot new TreeNode(preorder[root]);int inorder_root hash[preorder[root]]; //根节点对应的在中序的下标//构建左右子树BTroot-left dfs(preorder, root 1, left, inorder_root - 1);//右子树的根节点下标前序 root left_Tree_size 1 ( inorder_root - left root 1)BTroot-right dfs(preorder, inorder_root - left root 1, inorder_root 1, right);return BTroot;}TreeNode* buildTree(const vectorint preorder, vectorint inorder) {//inorder填充hashfor (int i 0; i inorder.size(); i){hash[inorder[i]] i;}return dfs(preorder, 0, 0, inorder.size() - 1);}
};
